백준 1965 상자넣기

// 다시 풀기
 
// D[i]를 뭘로 놓냐가 핵심 ! 
 
// 처음 접근할 때 D[i]를 A[i]까지 검사했을 때 가장 긴 부분 수열의 길이
// 로 설정했더니 안 풀림.
 
// D[i] = A[1], , , A[i] 까지 수열이 있을 때, A[i]을 마지막으로 하는
// 가장 긴 증가하는 부분 수열의 길이.
 
#include <cstdio>
#include <algorithm> // *max_element()를 이용하기 위함.
#include <vector>
using namespace std;
 
int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        d[i] = 1; // 자기자신만 있을 경우 1이므로. 최소 1이됨.
        for (int j = 0; j < i; j++) {
            // 현재 d[i]가 d[j] + 1보다 크거나 같다면 대치시킬 필요 x
            if (a[j] < a[i] && d[j] + 1 > d[i]) {
                d[i] = d[j] + 1;
            }
        }
    }
    printf("%d\n", *max_element(d.begin(), d.end()));
    return 0;
}

이 문제를 처음보자마자 든 생각은 

" 11053 가장 긴 증가하는 부분 수열 문제와 똑같다 " 이다. 실제로 그렇다.

하지만 알고리즘을 한 달만에 다시 하려다 보니 접근법이 도저히 떠오르지 않고 

오래 고민할 시간도 없어서 전에 풀었던 11053 문제 코드 보고 풀었다...

간단히 리뷰해보면,

DP 문제에서는 d[]를 뭘로 정의하느냐가 가장 핵심이다.

그리고 배열로 선언하지 않고 vector로 선언해야 

*max_element(d.begin(), d.end())

위 함수를 이용하여 배열 원소들 중에 최댓값을 쉽게 찾을 수 있다.