CodeDrive

문제:

Day of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i]로 연주 해야 한다. 하지만 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

입력:

첫째 줄에 N, S, M이 주어진다. (1<=N<=100, 1<=M<=1000,0<=S<=M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력:

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면(중간에 볼륨을 조절을 할 수 없다면) -1을 출력한다.

풀이방법:

 2차원 배열을 사용하는 동적계획법을 사용하면 트리처럼 진행이 된다. 점차 연주가 가능한 볼륨이 많아지긴 하겠지만, 0보다 작은 값이나 초과하는 값들도 들어오기 때문에 생각만큼 많이 증가하지는 않게 된다.

 각 배열은 0으로 초기화 되어 있으며 각 곡마다 연주할 수 있는 볼륨은 1로 바뀌게 된다. 따라서 처음에는 S 자리에만 1로 초기화 되어 있으며 다음 곡의 배열은 이전 곡에서 1인 값에 V[i]를 빼거나 더한 값이 1로 초기화 될 것이다.

 이렇게 마지막 곡까지 위 행위를 반복하고 뒤에서부터 1인 값을 찾아 1이면 값을 넣고 종료시키면 그 값이 최댓값이 될 것이다. 그리고 애초에 -1을 초기값으로 잡아뒀기 때문에 1인 값을 만나지 못하면 연주 할 수 없는 것을 의미하므로 답은 그대로 -1이 될 것이다.

문제링크:

https://www.acmicpc.net/problem/1495