백준 11053 - 가장 긴 증가하는 부분 수열

문제

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

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

 

풀이

d[n] = arr[n]을 포함하는 가장 긴 부분 수열의 길이라고 하면 d[n]을 구하기 위해서 다음의 규칙이 필요하다.

1. i = 1 부터 i = n-1 까지 arr[i] < arr[n] 이고

2. i = 1 부터 i = n-1 까지 d[i]가 최대인 값.

 

위 두가지 조건을 동시에 만족하는 i 값인 d[i] + 1 = d[n] 값이 된다. 

 

예를 들어, 10 20 10 30 20 50 에서 d[4]를 구할 때 

d[1] = 1, d[2] = 2, d[3] = 1 이고 arr[1], arr[2], arr[3] < arr[4] 이므로

d[4] = d[2] + 1 = 3 이 된다.

 

같은 방식으로, d[6]을 구할 때

d[1] = 1, d[2] = 2, d[3] = 1, d[4] = 3, d[5] = 2 이고 arr[1], arr[2], arr[3], arr[4], arr[5] < arr[6] 이므로

d[5] = d[4] + 1 = 4 가 된다.

 

따라서

d[n] = {

    i = 1 부터 i = n-1 까지 

      arr[i] < arr[n] && max(d[i]) 일 때 

         d[i] + 1

}

 

그러므로 1부터 N까지 최대 d[N] 값을 찾으면 답이 된다.

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int dp[1001];
int arr[1001];
int N, temp, idx;
int result;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> arr[i];
    
    for (int i = 1; i <= N; i++)
    {
        temp = 0;
        idx = i;
        for (int j = 1; j < i; j++)
        {
            if (arr[j] < arr[i] && temp < dp[j])
            {
                temp = dp[j];
                idx = j;
            }
        }
 
        dp[i] = dp[idx] + 1;
    }
 
    for (int i = 1; i <= N; i++) result = max(result, dp[i]);
 
    cout << result;
 
    return 0;
}