반응형
가장 큰 증가 부분 수열
-
BOJ) 가장 큰 증가 부분 수열알고리즘/백준 2020. 7. 26. 17:33
가장 큰 증가 부분 수열 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 풀이 다이나믹 프로그래밍 문제는 너무 어렵다.. ㅠㅠ 다른 문제 유형보다 생각을 조금 많이 요한다. 많은 실패를 겪고 답을 찾았다. 먼저, 각 index에서 취할 수 있는 가장 큰 증가 부분 수열의 합을 저장할 dp를 선언해준다. 이후 for문을 통해 index를 탐색하면서( i ) dp[i] 에 최대값을 저장한다. 최대값을 저장하는 과정은 0부터 해당 index 전 까지 for..