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

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

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

 

 

 

EXPLANATION

N번째 숫자들 중에서 임의로 선택해서 가장 긴 증가하는 부분 수열을 만들어야 한다.

 

N번째 숫자들 중에서 임의로 선택해서 증가하는 모든 부분 수열을 구하는 경우는 

1<= i <=N 일 때, 각 i번째까지의 숫자들 중에서 i번째 숫자가 가장 큰 증가하는 부분 수열을 구하는 각 각의 경우들을 다 모은 합집합에 포함되어 있다.

 

ex)

?: 선택 유무 모름     O: 선택     X: 비선택

따라서, 위의 각 각의 경우의 가장 긴 수열을 만드는 경우를 구한 후, 거기서 가장 긴 수열을 가지는 것이 답이다.

 

 

i번째 숫자를 arr[i]라고 하고

i번째까지의 숫자들 중에서 i번째 숫자가 가장 크면서 가장 긴 증가하는 부분 수열의 길이를 dp[i]라고 하자.

 

일단 i번째 이전에 수가 없거나 모든 수가 arr[i]보다 큰 경우에  dp[i]  수열이 arr[i]만 가지므로 dp[i] = 1이 된다.

그게 아니라면, 이후 1 <=  j < i 범위를 오름차순으로 돌면서 arr[i]가 arr[j]보다 큰 경우에, dp[j]의 수열에 arr[i]를 추가해서

dp[i]를 dp[j] + 1로 갱신하면 된다.

그러면 1<= j < i일 때 arr[i]가 arr[j]보다 큰 경우의 dp[j] + 1들 모두 비교해서 가장 큰 값이 dp[i]가 된다.

 

 

1<= i <=N에서 dp[i]를 모두 비교해서 가장 큰 값이 N번째 숫자들 중에서 임의로 선택해서 가장 긴 증가하는 부분 수열을 만드는 경우이다.

 

 

ex)

6
10 20 10 30 20 50

 

i = 1, dp[1] 구하기:

dp[1]은 i 자신만 포함가능하므로 1

maxDP = dp[1]

 

 

i = 2,dp[2] 구하기:

arr[2] > arr[1]

max(1, dp[1])

dp[2] = dp[1] + 1 = 2

maxDP = max(dp[1], dp[2]) = dp[2]

 

i = 3,dp[3] 구하기:

arr[3] <= arr[1], arr[2] 

따라서 dp[3]은 i 자신만 포함가능하므로 1

maxDP = max(dp[2], dp[3]) = dp[2]

 

 

i = 4,dp[4] 구하기:

arr[4] > arr[1], arr[2], arr[3]

max(dp[1], dp[2], dp[3]) = dp[2]

dp[4] = dp[2] + 1 = 3

maxDP = max(dp[2], dp[4]) = dp[4]

 

i = 5,dp[5] 구하기:

arr[5] > arr[1], arr[3]

arr[5] <= arr[2], arr[4] 

max(1, dp[1], dp[3]) = 1

dp[4] = 1 + 1 = 2

maxDP = max(dp[4], dp[5]) = dp[4]

 

 

 

i = 6,dp[6] 구하기:

arr[6] > arr[1], arr[2], arr[3], arr[4], arr[5]

max(1, dp[1], dp[2], dp[3], dp[4], dp[5]) = dp[4]

dp[4] = dp[4] + 1 = 4

maxDP = max(dp[4], dp[6]) = dp[6]

 

따라서 답은 dp[6] = 4

 

 

 

 

위 설명만 부분 코드로 나타내면

int maxDP = 0;

for (int i = 1; i <= N; i++)
    {
        
        
        dp[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (arr[i] > arr[j])	
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        
        
        maxDP = max(maxDP, dp[i]);
    }

 

 

 

 

.

 

 

CODE

#include <iostream>

using namespace std;

int main()
{

    int N;
    int dp[1001] = {};    //for [1, N]
    int arr[1001] = {};
    int maxDP = 0;

    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }

    for (int i = 1; i <= N; i++)
    {
        dp[i] = 1;

        for (int j = 1; j < i; j++)
        {
            if (arr[i] > arr[j]) 
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxDP = max(maxDP, dp[i]);
    }

    cout << maxDP << "\n";
}