기타리스트 실버1 (백준, DP)

n, s, m = map(int, input().split())
v = list(map(int, input().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]==1:
        ans = i
        break
print(ans)

이 문제는 2차원 리스트 형태의 메모라이제이션 공간이 필요하다.

 

m의 크기만큼 배열을 생성하고 n의 길이만큼 값을 추가해준다.

 

첫 기준 값인 s의 인덱스를  0번째 줄에 1로 초기화하고 반복문으로 조회 시 해당 값이 1이고 v리스트의 i번째 값과 더하거나 뺐을때 기준 값을 넘어가지 않으면 해당하는 값의 인덱스를 1로 초기화한다,

 

이를 끝까지 반복한 후 m의 값을 n번째 리스트를 내림차순으로 조회하여 1이 있는 경우 해당 값을 ans로 없으면 초기의 -1로 출력한다.