[python] 백준 1495 기타리스트

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

1495번: 기타리스트

 

문제 해결

• 전형적인 DP문제
• dp[i][j]를 i번째 볼륨조절 후 j의 볼륨 가능 유무로 정의할 수 있다.

 

CODE

import sys
input = sys.stdin.readline

n, s, m = map(int, input().split()) # 곡 개수, 시작 볼륨, 최대 볼륨
V = [0] + list(map(int, input().split()))
dp = [[0 for _ in range(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] == 1:
            if j + V[i] <=m:
                dp[i][j+V[i]] = 1
            if j - V[i] >=0:
                dp[i][j-V[i]] = 1
for i in range(m,-1,-1):
    if dp[n][i] == 1:
        print(i)
        exit()
else:
    print(-1)