[백준 1495번] 기타리스트 - java

문제 설명

1. 연주할 곡 N, 시작 볼륨 S, 최대 볼륨 M이 주어진다.

2. N개의 변경할 볼륨의 크기가 주어진다.

3. 모든 곡의 볼륨은 최대 볼륨 M을 넘어서는 안된다.

4. 마지막 곡에 연주 가능한 최대 볼륨을 구하면 된다.

풀이 과정

 1. DP를 사용하는 문제이고, 적용 시점을 잘 고민해 봐야 한다.

 2. 먼저 DP의 범위를 볼륨 M으로 설정하고,  DP[A]의 값은 그 연주 시점으로 설정한다.

 3. 예를 들어, 2번째 곡이 4, 8의 볼륨으로 연주 가능하면 DP[4] = 2, DP[8] = 2 이런 식이다.

 4. 처음에 DP[S] = 0으로 설정하여 시작 볼륨을 구한다.

 5. 다음 볼륨을 구하려면 현재 시점의 곡 순서에서 이전 시점에 불린 곡(DP[X]=현재시점-1 의 X값) 의 정보를 통해 구해줄 수 있다.

 6. 그리고 그 변경 곡들은 더하거나 빼서, 0보다 크거나 같고 M보다 작거나 같을 때 적용하면 될 것이다.

 7. 여기서 중요한 점은 그 볼륨의 적용 시점을 모든 process가 끝난 후에 적용해야 한다는 것이다.

ex) 예를 하나 들어 보자면 DP[2] = 3 DP[4] = 3이다. 그렇다면 4번째 스테이지에서는 이 두 개의 DP를 가져와야 한다.

     그런데 만약에 4번째 스테이지에서 변경할 볼륨이 2이면 처음 DP[2]에서 바로 변경하면 DP[4] = 4가 되어 DP[4] = 3을 시행하지 못 할 것이다. 따라서 이 적용을 따로 배열에 담아 주고, 모든 검색이 끝난 후에 일괄 적용하면 될 것이다. 

코드