[C++] 백준 11053 - 가장 긴 증가하는 부분 수열 (DP) 문제 풀이

백준 11053번 가장 긴 증가하는 부분 수열 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 

이 문제는 특히 실버2의 난이도를 갖고 있는 만큼 생각을 많이 해야지만 규칙을 파악할 수 있다.

문제 링크

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

 

알고리즘

1. 규칙을 파악하기 까다로운 문제이다.
2. 먼저, 가장 긴 증가하는 수열이 되기 위해서는 처음부터 각 원소의 최대 증가길이를 생각해볼 필요가 있다.
3. 예를 들어, 위의 예시에 주어진대로 10 20 10 30 20 50 수열에서는, 10 20 의 각각의 수열의 길이는 1,2 가 된다.
4. 하지만 3번째 원소 10의 경우에는 앞에서 10보다 작은 원소가 1개도 없기 때문에(0) 자기 자신만 있어서 길이가 1이 된다.(0+1)
5. 4번째 원소를 살펴보면 30인데, 이때 이전의 모든 원소들이 30보다 작으므로 이전의 원소들이 갖고 있는 증가 수열의 길이들 중 가장 긴 길이 +1 을 하면 되는 것이다. 이 경우에는 10 20 30 이 되어서 3 이 된다.
6. 5번째 원소를 살펴보면 20 인데 앞선 원소들 중 20보다 같거나 큰 20, 30 원소는 제외를 하고 나머지 원소들 중에서 가장 긴 길이 +1을 하면 되는 것이다.
7. 규칙을 파악하였는가?
8. dp[n]번째 가장 긴 증가하는 수열의 길이는, 1~n-1 원소들 중 n번째 값보다 작은 값만 가지는 것들로만 추려서 그 중에서 가장 긴 길이를 가진 것을 찾아 +1을 해주는 것이다.
9. for문 돌 때마다 최댓값 받아주는 max_val=0 초기화 해주는 것과, 마지막에 출력할 때 dp[n]이 아니라 1부터 n까지 dp[i]의 최댓값을 구해줘야 한다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n,max_val=0;
    int dp[1001];
    dp[1]=1;

    cin>>n;
    int arr[n+1];
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        for(int j=1;j<i;j++){
            if(arr[i]>arr[j]){
                max_val=max(max_val,dp[j]);
            }
        }
        dp[i]=max_val+1;
        max_val=0;
    }
    for(int i=1;i<=n;i++){
        max_val=max(max_val, dp[i]);
    }
    cout<<max_val<<'\n';
    
    return 0;
}

 

제출 결과