백준_DP_기타리스트_1495_파이썬

✅문제

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

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

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

✅ 알고리즘 분류

• 다이나믹 프로그래밍
  ㅤ

💡풀이

DP 문제는 보통 시간복잡도가 굉장히 짜기 때문에 점화식을 잘 짜야한다
이 문제를 처음에 풀 때는 재귀를 통해서 풀었는데 시간초과가 자꾸 나서
결국 포멧을 바꿔서 다시 풀이했다

정답 풀이

import sys
n, s, m = map(int, input().split())

V = list(map(int, sys.stdin.readline().split()))

dp = [[0]*(m+1) for _ in range(n+1)]

dp[0][s] = 1

for i in range(n):
    for j in range(m+1):
        if dp[i][j] == 1:
            if j+V[i] <= m:
                dp[i+1][j+V[i]] = 1
            if j-V[i] >= 0:
                dp[i+1][j-V[i]] = 1


ans = -1
for i in range(m, -1, -1):
    if dp[n][i]:
        ans = i
        break
print(ans)

먼저 dp배열을 n개의 곡을 0부터 m까지 토글을 할 수 있는 2차원 배열을 선언 후
m보다 작고 0보다 크면 체크를 했다
그 후 마지막 곡(n번째 배열)의 값을 큰 곳 부터 탐색하며 값이 발견되면 바로 출력하는 방식이다.

📌 배운 점

• 무조건 점화식이 있어야 한다는 강박때문에 재귀 식을 짰던 것 같다. 먼저 눈으로 한번 풀어보면서 내가 이렇게 계산한 이유를 다시한번 생각하면서 짜니까 풀기 쉬웠다. 적으면서 풀자