백준 11053 (DP)

11053번: 가장 긴 증가하는 부분 수열

과정

• 맨 처음 문제를 보고 너무 쉽다고 생각했다. 그냥 수열 받을 때 마다 최대값 저장해서 비교하면 되는거 아닌가? 해서 나온 코드..

#include <iostream>

#include <vector>

using namespace std;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr); cout.tie(nullptr);

    int N = 0;      // 수열의 크기

    vector<int> A;  // 수열을 받을 벡터

    int answer = 0; // 가장 긴 증가하는 부분의 길이

    int temp = 0;   // 수열을 받을 때 최고값 임시 저장

    cin >> N;

    A.resize(N);

    for (int i = 0; i < N; i++)

    {

        cin >> A[i];

       

        if(A[i] > temp)

        {

            temp = A[i];

            answer++;

        }

    }

    cout << answer;

    return 0;

}

• 하지만 반례 하나를 보고 알아차렸다.
  {10 20 10 30 20 50 11 12 13 14 15} 의 정답은 4가 아니라 6이다. 왜냐하면 "가장 긴" 증가하는 부분은 10 20 30 50 이 아니라 10 11 12 13 14 15이기 때문이다..
• 이런 경우 DP를 이용해서 푸는게 일반적이다. 음 가령 30을 예로 들면, 10 20 30이 될것인지, 10 30 이 될것인지, 20 30 이 될것인지를 정할 수 있는데, 이를 정리하면,
  X번째 숫자 기준 1~X-1번째 숫자중, X번째 숫자보다 작은 수의 최대 길이+1이 X번째 숫자의 최대 길이가 된다.
  로 정의할 수 있다.

코드

#include <iostream>

#include <vector>

using namespace std;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr); cout.tie(nullptr);

    int N = 0;      // 수열의 크기

    vector<int> A;  // 수열을 받을 벡터

    vector<int> DP; // 최고 길이를 받을 벡터

    int answer = 0; // 가장 긴 증가하는 부분의 길이

    int temp = 0;   // 수열을 받을 때 최고값 임시 저장

    cin >> N;

    A.resize(N);

    DP.resize(N);

    for (int i = 0; i < N; i++)

    {

        cin >> A[i];

    }

    for (int i = 0; i < N; i++)

    {

        // 본인값을 포함해서 최소값은 1이다.

        DP[i] = 1;

        for(int j = i - 1; j >= 0; j--)

        {

            // i번째 숫자보다 작은 숫자를 찾으면,

            if (A[i] > A[j])

            {

                DP[i] = max(DP[i], DP[j]+1);

            }

        }

        answer = max(DP[i], answer);

    }

    cout << answer;

    return 0;

}

막상 풀고 보니 지금껏 풀었던 DP문제중에 가장 쉬웠는데.. 문제의 테스트케이스만 생각해서 너무 단순하게 풀이했다.