> 문제 <

출처 : 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)

참고 : https://kils-log-of-develop.tistory.com/261