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

dp 문제가 어려워서 계속 공부하고 있는데, 내 발목을 잡았던 문제다. 풀이를 읽어도 뭔가 사악 자연스럽게 안 들어와서 며칠 동안 보고 있었는데 이제야 좀 들어오는 것 같아서 안 까먹기 위해 블로그를 쓴다. 이 문제는 LIS 알고리즘으로 검색하면 여러 가지 방법이 나오지만, 난 현재 dp방법만 알고 있으므로 이것만 소개하겠다. 이후 된다면 계속 추가하도록 한다.

 

문제 사이트는 다음과 같다. 말 그대로 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾으면 된다.

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

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

 

1. dp를 이용

dp를 이용해서 푸는 건 알겠는데, dp를 어떻게 잡아야 하는지부터 머리에 안 들어왔다. 풀이를 찾아보고, 며칠동안 생각하니까 외워진건지 아님 이해한건진 모르겠는데 dp를 이렇게 잡아야 한다는 건 알겠다.

dp[i] : i번째 원소를 포함하는 가장 긴 부분 수열의 길이

여기서 무조건 i번째 원소를 포함한다는 게 중요하다. 여기서 dp[n]이 무조건 가장 긴 증가하는 부분 수열이 아니라는 것도 캐치해야 하고, 다른 문제들처럼 그냥 i번째까지 봤을 때 가장 긴 부분 수열이 아니라는 것도 중요하다.

dp를 이렇게 잡게 되면, 이전 dp들과 현재 dp(dp[i])와 무슨 관계가 있는지를 생각해 보게 된다. 생각해보면, 가장 긴 증가하는 부분 수열이고 i번째 원소를 무조건 포함하므로 그 바로 이전 값(i번째 원소 바로 전 값)은 무조건 a[i]보다 작아야 한다는 걸 깨달을 수 있다. 이렇게 되면  그 전 원소들 중(a배열)에서 i번째 원소들보다 작은 원소들 중에서, 가장 dp값이 큰 친구를 선택해서 i번째 원소를 붙여주면 가장 긴 부분 수열을 만들 수 있다는 걸 깨달을 수 있다. 

결국 dp[i]는 

dp[i]=(k=0번째부터 i전까지)max(dp[k]+1) && a[k]<a[i]

이렇게만 작성해서 백준에 제출하면 틀렸습니다. 가 뜬다. 그럼 무엇이 빠졌는가? 밑에 코드를 보자. 정답 코드이다.

#include <cstdio>
#include <algorithm>

int main(){
    int n, ans;
    int a[1001];
    int dp[1001];

    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        dp[i]=1;
    }

    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            if(a[i]>a[j] && dp[i]<dp[j]+1) dp[i]=dp[j]+1;
        }
    }
    int max=0;
    for(int i=0;i<n;i++) if(dp[i]>max) max=dp[i];
    printf("%d\n",max);
}

if(a[i]>a[j]) dp[i]=dp[j]+1; 만으로 코드를 돌리면 틀렸다가 뜬다. 옆에 && dp[i]<dp[j]+1을 붙여줘야 한다. 이 이유는 j가 0부터 i전까지 돌면서 가장 큰 dp[j]값을 들고와야 하기 때문이다. && dp[i]<dp[j]+1을 작성하지 않으면 가장 큰 값이 아니라 가장 최근의 dp값으로 초기화한다. 예시는 다음과 같다.

10. 20. 30. 20. 40. 여기서 가장 긴 부분수열의 길이는 10. 20. 30. 40으로 4이다.

40을 포함하는 dp를 구한다고 생각했을 때 (dp[4], 5번쨰 원소이므로 dp[4])

j=0 => dp[4]=dp[0]+1=2

j=1 => dp[4]=dp[1]+1=3

j=2 => dp[4]=dp[2]+1=4

j=3 => dp[4]=dp[3]+1=3 !!!!!! 작아져 버린다!!!!!!!

이렇기 때문에 dp[i]<dp[j]+1 조건이 무조건 필요하다.

가장 긴 증가하는 부분 수열 문제는 이렇게 풀면 된다.