백준 알고리즘 11055 (dp)

 

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

풀이:    

저번 11053번 풀이에서 [현재위치한 수] 와 [전에 위치했던 수] 를 비교를 할 때 현재 위치에서 저번 위치들을 모두 비교하기 때문에 11053 코드를 조금 수정하면 답을 구할 수 있다.

min에 해당하는 위치까지의 수열의 길이가 아닌 해당하는 위치까지의 합을 넣고 

 dp[i]  =  dp[i-1] + a[i]  (저번까지의 합 + 현재위치의 값) 을 추가 하면된다.

d[i] (현재까지 위치의 합)이 max 보다 클 경우 max에 값을 넣어주면 된다.

max는 최종적으로 마지막 출력 값으로 수열에서 합 한 값이 가장 큰 값이 들어가게된다.

 

코드

 

 

느낀점 : 11053번의 응용문제였으나 풀지 못했다. 11053번과 마찬가지로 o^2복잡도를 갖기 때문에 더 낮은 복잡도를 가지는 방법을 시도해봐야겠다.