[백준 1495] 기타리스트 (DP)

https://www.acmicpc.net/problem/1495 문제이해 곡의 개수 N과 시작 볼륨 S, 그리고 최대 볼륨 M이 주어졌을때 마지막 곡의 볼륨이 될 수 있는 최대값을 출력하라. 풀이 DFS나 BFS로 모든 가능한 경로를 탐색하는 최악의 경우를 생각해 봤는데 2^50번의 연산이 필요하기에 이 방법은 접어두고 다른 방법을 계속 생각했었다.

그래서 결국 DP로 풀어봐야겠다고 생각했고 1차원 배열을 가지는 DP와 각 순서의 곡에 대해서 음량을 더한 것과 뺀 것을 저장하는 opposite 변수를 만들어 그리디의 형식으로 풀어보았지만 이 방법은 Optimal Substructure(최적 부분 구조)을 충족하지 못한다. 그래서 하루종일 고민하다 다음날 다음과 같이 최악의 경우를 직접 써봤는데 이 2^N의 경로를 해결할 방법이 떠오르지 않아 결국 구글링을 해봤다.

그 결과 2차원의 DP 배열을 사용해서 해결하는 것을 알게 되었고 해답을 알고 나니까 그림에서 분홍색으로 네모친 부분이...