[1495] 기타리스트 in python

> dp (다이나믹 프로그래밍)

 

dp문제는 너무너무 어렵다...

실버1이지만 실버1 같지 않은 문제.. ㅠ.ㅠ

열심히 더 노력하자!

 

 

dp로 해야해서

리스트를 도대체 어떻게 만들라는건가 햇더니

dp 리스트가 여러개 필요했다.

 

start, 볼륨 리스트 개수... 

하나의 dp 리스트로만 풀 수 잇을거란 생각을 깨자

이렇게 여러개로 하면 더 쉬울때도 있다..

 

트리식으로 가지치기가 필요한 순간이라면

Dp를 떠올려보자!

 

두려워하지말기 :) 

n, s, m = map(int, input().split())
v = list(map(int, input().split()))
dp = [[False for _ in range(m + 1)] for _ in range(n + 1)]  # start, nList
dp[0][s] = True
for i in range(n):
    for j in range(0, m + 1):
        ch = dp[i][j]
        if ch:  # True
            if j + v[i] <= m:
                dp[i + 1][j + v[i]] = True
            if j - v[i] >= 0:
                dp[i + 1][j - v[i]] = True
answer = -1
for i in range(m, -1, -1):
    if dp[n][i]:
        answer = i
        print(answer)
        break
if answer==-1:
    print(-1)