백준 1965 C++

https://www.acmicpc.net/problem/1965

1965번: 상자넣기

 

문제 정리

주어진 상자들의 크기를 고려하여 각 상자 안에 다른 상자를 넣을 수 있는 최대 개수! 자르긴가

 

생각

각 상자를 마지막으로 포함하는 최대 상자 개수를 저장하는 배열 만들기 -> 저번에 했던 dp랑 비슷한데? 똑같은 형식인듯!!

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    int box[n];
    int dp[n];

    for (int i = 0; i < n; ++i) {
        cin >> box[i];
        dp[i] = 1;
    }

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (box[i] > box[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int result = 0;
    for (int i = 0; i < n; ++i) {
        result = max(result, dp[i]);
    }
    cout << result << endl;
}

 

선택한 원소의 최댓값 + 1을 한 값(box[i])이 현재 상태의 최댓값보다 크면 그 값으로 자기자신의 값을 갱신

 

중요한 점

얘 역시 1이 시작이여야 함

자기자신을 선택하는 순간 상자의 개수가 최소 1개는 되어야 하기 때문

-> 1로 초기화 해줌

 

 

전에 푼 백준 2631과 점화식이 똑같다!! dp의 맛을 알아가는중

 

백준 2631 풀이는 

https://5ffthewall.tistory.com/62