[백준-1495] 기타리스트

---

나의 코드

import sys
input = sys.stdin.readline

n,s,m=map(int,input().split())
volumes=list(map(int,input().split()))

dp=[-2]*(m+1)
dp[s]=-1
for i in range(n):
    tmp=[]
    for j in range(m+1):
        if dp[j]==i-1:
            if j-volumes[i]>=0:
                tmp.append(j-volumes[i])
            if j+volumes[i]<=m:
                tmp.append(j+volumes[i])
    for k in tmp:
        dp[k]=i
ans=-1
for i in range(m,-1,-1):
    if dp[i]==n-1:
        ans=i
        break
print(ans)

수행시간: 84ms

풀이

i번째 곡을 연주할 때 가능한 볼륨이 j라 할때 dp[j]=i이다.
예를 들어 2(i)번째 곡을 연주할때 1(i-1)번째 곡을 연주할 때의 볼륨들인 dp[j]=1인 j값(볼륨)들을 찾고 그 j값에 volumes[2](현재조절가능한볼륨)을 빼거나 더한값이 0이상 m이하이면 dp[j-volumes[2]]=2 or dp[j+volumes[2]]=2 로 설정하는데 이렇게 바로 설정하면 답이 제대로 안나오는 경우가 생긴다.
예를 들어 위의 상황에서 dp[j]=1인 j값들중 j-volumes[2]이도 포함되어있는데 dp[j-volumes[2]]=2로 바로 바꾸면 j-volumes[2]에 대한 조사를 제대로 할 수 없다.

---

다른사람들은 나랑 조금 다르게 풀었는데 근본적인 풀이는 비슷한것같다.