[Python] 백준 1495_ 기타리스트

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

이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.

1. DP정의

• d[i][j] :i번째 곡을 j볼륨으로 만들 수 있는지 여부(1:가능/0:불가능)

2. 코드

주석을 통해 최대한 자세히 설명을 적었다.

import sys
input = sys.stdin.readline

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

#dp정의 
d=[[0]*(m+1) for _ in range(n+1)]
#처음 시작
d[0][s] =1

for i in range(1,n+1): #곡의 개수 만큼 
    for j in range(m+1):
        if d[i-1][j]!=0: #볼륨 조절 가능하면 
            if 0<=j+v[i-1]<=m:
                d[i][j+v[i-1]]=1
            if 0<=j-v[i-1]<=m:
                d[i][j-v[i-1]]=1
ans =-1
#볼륨의 최대값을 출력하기 위해 내림차순으로 반복문 실행 
for i in range(m, -1, -1):
    if d[n][i]==1: #최대값 발견하면 중단 
        ans = i
        break
    
print(ans)