Beakjoon 11055 가장 큰 증가 부분 수열

13 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/11055

나의 풀이

수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 일 경우를 생각해보자
마지막 값이 A[i]인 증가 부분 수열의 합을 DP[i]라고 한다.
i=1인 경우 부분 수열은 {A[i]}이기 때문에 DP[1] = A[i] = 1 인 것을 알 수 있다.

i=2인 경우를 생각해보면 증가 부분 수열의 마지막이 A[2]인 경우는 첫 번째로 부분 수열 {A[2]}로 DP[2] = A[2]가 될 수 있고,
만약 A[1] < A[2]를 만족한다면 DP[2] = DP[1] + A[1]로 총 2가지 경우가 있을 수 있고 DP[2]의 값은 더 큰 값이기 때문에 아래와 같이 표현된다.
DP[2] = max(A[2], DP[1] + A[2]) = 101

i=3인 경우 마찬가지로 첫 번째로 {A[3]}가 될 수 있고,
만약 A[2] < A[3]을 만족한다면 마지막 값이 A[2]인 부분 수열의 합을 이어받아 DP[2] + A[3]로 표현할 수 있다. 하지만 이 수열에서는 만족하지 않는다.
또한 마지막 값이 A[2]로 끝나는 수열의 합보다 A[1]로 끝나는 부분 수열의 합이 더 클 수 있기 때문에 A[1] < A[3]의 경우도 생각한다.
만약 A[1] < A[3]을 만족한다면 마지막 값이 A[1]인 부분 수열의 합을 이어받아 DP[1] + A[3]로 표현할 수 있다. DP[3]의 값을 정리하면
DP[3] = max(A[3], DP[1] + A[3]) = 3 이 되는 것을 알 수 있다.

이를 일반화 시키면
DP[i] = max(DP[j]) + A[i]로 정리할 수 있으며 i와 j는 아래 두 조건을 만족한다.
(0 <= j < i) and (A[j] < A[i])

풀이 코드 : 11055 가장 큰 증가 부분 수열

#include <stdio.h>
#include <vector>
using namespace std;

int DP[1000];
vector<int> A;

int main(){
    int N, num;
    scanf("%d",&N);
    for(int i = 0;i<N;i++){
        scanf("%d",&num);
        A.push_back(num);
        DP[i] = num;
    }

    for(int i = 0;i<N;i++){
        for(int j=0;j<i;j++){
            if(A[i] > A[j]){
                DP[i] = max(DP[j]+A[i], DP[i]);
            }
        }
    }

    int answer = 0;
    for(int i = 0;i<N;i++){
        answer = max(answer, DP[i]);
    }

    printf("%d", answer);
}

채점결과