출처 : https://www.acmicpc.net/problem/1495
dp(dynamic programming) 사용
N: 곡의 개수, S: 시작 볼륨, M: 최대 볼륨
리스트 V: 각 곡의 볼륨차이들 (+, -)
1. 현재 볼륨 + 다음 곡의 지정된 볼륨(V[i])
2. 현재 볼륨 - 다음 곡의 지정된 볼륨(V[i])
단, 0 ≤ 볼륨 ≤ M && 마지막 곡 연주 불가? -1 출력
- 0~M까지 모든 볼륨의 경우의 2차원 리스트 필요
- 합차로 인해 나올 수 있는 볼륨 index의 value값에 1(True) <기본 default 값은 0>
- 마지막 행(=마지막 곡)의 끝 열에서부터 하나씩 살피며 value값이 1인 index 출력(=마지막 곡의 최대 볼륨값)
import sys
input = lambda: sys.stdin.readline()
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(1, N+1): # 곡 순서(행)
for j in range(M+1): # 볼륨 (열)
if dp[i-1][j] == 0:
continue
if j-V[i-1] >= 0:
dp[i][j-V[i-1]]=1 # 나올수있는 (합,차) 경우의 수 부분 표시
if j+V[i-1] <= M:
dp[i][j+V[i-1]]=1
for i in range(M,-1,-1): # 끝에서부터
if dp[N][i]==1:
print(i)
break
if i==0: # 마지막 행에 1 값이 없다면 == 마지막 곡 연주x
print(-1)