BOJ 11055 가장 큰 증가 부분 수열(C++)

가장 큰 증가 부분 수열 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	1744	836	682	47.961%

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력 

10
1 100 2 50 60 3 5 6 7 8

예제 출력 

113

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 다이나믹 프로그래밍

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include    <stdio.h> #include    <algorithm> #pragma warning(disable:4996)   int A[1111]; int S[1111]; int main() {     int N;     scanf("%d", &N);     for (int i = 1; i <= N; ++i)         scanf("%d", &A[i]);       S[1] = A[1];     for (int i = 1; i <= N; ++i)     {         S[i] = A[i];         //S[i] 는 i번째를 포함하는 부분수열의 가장 큰 합.         for (int j = 1; j < i; ++j)         {             if (A[i] > A[j])                 S[i] = std::max(S[j] + A[i], S[i]);         }     }       int max = S[1];     for (int i = 2; i <= N; ++i)         if (S[i] > max)             max = S[i];     printf("%d", max);     return 0; }

다이나믹프로그래밍으로 풀면 어렵지 않다. 분명 어렵지 않은데 사실 좀 어려웠다. 

역시나 식을 어떻게 세워야 할지 한참 고민... 막상 코딩과정은 그렇게 길지 않았다. 

우선 S[i]는 i번째 수를 포함하는 부분수열의 가장 큰 합이라고 정했다. 

다이나믹을 풀다 보면 어렵지 않은 수준의 다이나믹문제는 대부분 입력이 x일 때의 값을 구해라! 이런 문제로.. D[x]는 x를 포함하는 무언가의 값! 으로 정의하면 어느정도 풀리기는 하는 것 같다.. 

좀더 나아가면 입력값이 x, y 두개일 경우도 있으나 이 경우도 대부분 비슷.. D[x][y]는 x, y를 포함하는 무언가의 값으로 정의하면 조금더 식 찾기가 편해진다. 고급의 문제는 본 적이 없으므로 아직 모르겠다. 

이것 또한 S[i]를 i번째 수를 포함하는 부분수열의 가장 큰 합이라고 했을 때, 문제 풀기가 상당히 간단해졌다. 

19번 줄 부터 23번째 줄까지가 사실상 핵심.