[파이썬]baekjoon 1496: 기타 고르기

https://www.acmicpc.net/problem/1496

1496번: 기타 고르기

---

dp문제

 

초기에 max값과 min값만을 의존하여 dp를 접근하였는데 실패..

 

모든 값에 대한 경우를 대비시켜줘야 됬던것!

 

문제에서 주어진 볼륨값을 index로 둔 뒤, 가장 큰 볼륨을 뽑으면 해결

import sys
input = sys.stdin.readline
n, s, m = list(map(int,input().split()))
arr = list(map(int,input().split()))

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

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

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