[C++] 백준 11053번 - 가장 긴 증가하는 부분 수열

---

0. 문제

 

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

 

1. 아이디어

 

 

출처: https://wootool.tistory.com/96

 

1) bottom-up 방식으로 문제를 풀이한다.

 

2) N번째 열까지 구할 수 있는 증가하는 가장 긴 부분 수열의 길이는 0번부터 N-1 번열 중 자신보다 작은 원소가 구했던 가장 긴 부분 수열의 길이 +1(본인의 길이)이 된다. 이때, N-1번 열까지 구했던 길이는 dp에 메모이제이션한다.

 

2. 소스코드

 

#include <iostream>
#include <algorithm>
int main()
{
    int N, max = 0, value[1000], dp[1000];
    std::cin >> N;
 
    for (int i = 0; i < N; i++)
        std::cin >> value[i];
 
    for (int i = 0; i < N; i++)
    {
        int min = 0;
        for (int j = 0; j < i; j++)
            if (value[i] > value[j])
                if (dp[j] > min) min = dp[j];
 
        dp[i] = min + 1;
        if (dp[i] > max) max = dp[i];
    }
    std::cout << max;
}

 

3. 결과

 

 

4. 피드백

 

• 뻔한 문제였는데 이상한데 꽂혀가지고 오래 걸렸다..

• 첫 번째 원소가 반드시 포함된다는 법은 없다.

• 핵심은 부분 수열의 원소가 오름차순이어야 한다는 것! 그러면 각각의 원소까지의 부분 수열은 자기보다 작은 것들로만 이뤄져 있다는 걸 체크했어야 했다. 흑 ㅜㅜ

---