[BOJ] 백준 1495번 : 기타리스트 (JAVA)

문제

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을 출력한다.

 

 

풀이

다이나믹 프로그래밍을 이용하여 풀 수 있는 문제였습니다.

 

볼륨이 [0, M] 구간에서 조절할 때, 최대 볼륨이 얼마인지 구하는 것이 핵심이었습니다. 이를 해결하기 위해서 메모이제이션을 사용하면 됩니다.

 

다만, 문제에서는 마지막 곡까지 볼륨을 조절하여 도달할 수 없는 경우 -1을 출력하라고 명시되어있습니다.

우리는 dp에서 값을 아직 저장하지 못한 경우, 흔히 -1을 할당합니다. 이 때, -1을 저장하는 목적이 겹치기때문에 시간초과가 발생할 수 있습니다.

 

따라서, dp에서 값을 아직 저장하지 못한 경우에는 -1을 대신 임의의 다른 수를 넣어주셔야 합니다.

 

위 내용과 관련된 내용은 아래 링크에서 자세히 보실 수 있습니다.

 

 

글 읽기 - 시간초과 질문입니다.

 

 

나머지는 전형적인 다이나믹 프로그래밍이므로 아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.