[백준 1965] 상자넣기 (C++)

문제 출처 : https://www.acmicpc.net/problem/1965

1965번: 상자넣기

#include <iostream>
#include <vector>
using namespace std;
 
int main () {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, cnt = 1;
    cin >> n;
    vector<int> v(n), dp(n, 1);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (v[i] > v[j]) dp[i] = max(dp[j] + 1, dp[i]);
            if (dp[i] > cnt) cnt = dp[i];
        }
    }
    cout << cnt;
    return 0;
}
 

 

알고리즘

- 다이나믹 프로그래밍

 

n으로 상자의 개수를 받고, 크기가 n인 벡터에 상자 크기를 담는다.

cnt는 최대 상자의 개수가 넣을 것인데, 하나도 못 넣는다면 자기 자신 1개이므로 1로 선언한다.

 

dp[i]는 v[i]를 포함한 최대 상자 개수이다.

이도 역시 자기 자신 1개가 최소값이므로 1로 선언한다.

 

이후 반복문을 돌며 자기보다 이전 인덱스를 확인한다.

자기보다 작은 값을 발견했다면 해당 상자를 포함한 최대 상자의 개수 (dp[j])에 자신을 포함한 값 (dp[j] + 1)과 현재 들고있는 최대 상자의 개수 (dp[i])를 비교하여 큰값으로 업데이트 한다.

cnt와 dp[i]를 비교하여 정답값도 업데이트 한다.

 

반복문이 끝나면 답을 출력한다.