[C++] 백준 - 11055 : 가장 큰 증가 부분 수열

문제 링크

11055번: 가장 큰 증가 부분 수열

 

풀이 ) DP

  LIS라고 부르는 문제이다.

  앞에서 부터 시작하여 숫자를 하나씩 추가해 나가면서 부분 문자열의 합의 최대를 찾는 문제이다.

  예제 입력을 예로하면 i는 4일 때 memo[4] = arr[4] = 60이다.

  1 100 2 50의 부분 수열을 순회하면서

•   j = 0일 때 1 < 60 이고 61 > 60 이므로 memo[4] = 61 이 된다.
•   j = 1일 때 100 > 60 이므로 다음으로 넘어간다
•   j = 2일 때 2 < 60 이고 63 > 61 이므로 memo[4] = 63 가 된다. ( ∵ memo[2] = 3)
•   j = 3일 때 50 < 60 이고 113 > 63 이므로 memo[4] = 113 가 된다. ( ∵ memo[3] = 53)

  위와 같은 방식으로 수열의 끝까지 간 후 memo[0] 부터 memo[n-1] 중 최댓값을 출력한다.

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

int arr[1002], memo[1002];

int main(void)
{
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", arr+i);

    for(int i = 0; i < n; ++i){
        memo[i] = arr[i];
        for(int j = 0; j < i; ++j){
            if(arr[j] < arr[i])
                memo[i] = max(memo[i], memo[j]+arr[i]);
        }
        ans = max(ans, memo[i]);
    }
    printf("%d\n", ans);
    return 0;
}

 

주의점 )

  - 반복문 시작 시 매번 memo[i]가 최소 자신을 포함하므로 memo[i] = arr[i]로 값을 넣고 시작한다.