[백준] 11055번 - 가장 큰 증가 부분 수열(수정)

문제

문제

수열 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의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

풀이과정

1.규칙

• DP이므로 점화식과 메모이제이션을 이용합니다.
• d[n-1] < d[n] 이라면 d[n]의 값을 증가시킵니다.

2.순서

[11053번 - 가장 긴 증가하는 부분 수열] 문제를 응용합니다.

A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 의 경우, A[n]+d[j(j는 0부터 n까지의 값)]이 d[n]보다 클 경우에만 메모이제이션 배열에 저장해주면 되므로

점화식은 d[n] = max(d[n], A[n]+d[j(0부터 n까지)]) 입니다.

d[n] = max(d[n], d[n] + d[j(0부터 n까지]) 가 답이 아닌 이유

d[n]+d[n-1]은 원 배열값을 계속 더해주는게 아니라 합산한 값을 계속 더해주므로

A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 의 경우에 수열의 가장 큰 합은 113이 아닌 135가 나오게 됩니다.

n이 9일때 수열의 합은 (1+3+7+16+33+67+8) 이 되기 때문입니다.

3.코드