문제
Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.
먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.
곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.
풀이
-
테이블 정의하기
dp[i] = i번째 볼륨들의 리스트 -
점화식 찾기
- dp[1]을 생각해보면 주어지는 초기값 p에 volume[1]을 더한 값 뺀 값을 저장해주면 된다.
- dp[2]도 마찬가지로 dp[1]에 저장된 볼륨값들에 volume[2]를 더하고 빼준 값을 저장해준다.
- 여기서 주의할 점은 문제의 조건이다. 볼륨은 0이 될 수 없고 주어진 최대값 M을 넘어설 수도 없다.
- 따라서 이런 형태가 된다.
dp[i] = cur_volume of dp[i-1] => [cur_volume + volumes[i], cur_volume - volumes[i]]
단, cur_volume + volumes[i], cur_volume - volumes[i] 둘 다 0보다 크고 M이하여야 한다.
⚠️ 위의 식 그대로 작성했더니 메모리 초과가 발생했다. 생각해보니 같은 값을 굳이 저장할 필요는 없다고 생각해서 중복 제거를 했더니 코드가 통과되었다.
N, S, M = map(int, input().split())
volumes = [0] + list(map(int, input().split()))
dp = [[ ] for _ in range(N +1) ]
dp[0] = [S]
for i in range(1, N+1):
for j in range(len(dp[i-1])):
plus_volume = dp[i-1][j] + volumes[i]
minus_volume = dp[i-1][j] - volumes[i]
if 0 <= plus_volume <= M and plus_volume not in dp[i]:
dp[i].append(plus_volume)
if 0 <= minus_volume <= M and minus_volume not in dp[i]:
dp[i].append(minus_volume)
if dp[N]:
print(max(dp[N]))
else: print(-1)피드백
점화식을 처음부터 떠올렸으나 이게 맞을리가 없다고 생각해서 오히려 더 돌아간 느낌이다. 아직도 계획이 완벽한 프로세스에 집착하는 경향이 있다. 풀이 계획은 중간중간에 변경될 수도 있고 떠오른 방법을 계속해서 적용해나가면서 성능을 향상시켜도 되니까 맞다고 생각하면 간단한 계획을 세운다음 해보자.
