Baekjoon-1496-기타리스트
28 Sep 2022import sys
input = sys.stdin.readline
N,S,M = map(int, input().split())
V = list(map(int, input().split()))
dp = [[-1]*(M+1) for _ in range(N+1)]
dp[0][S] = 0
for n in range(N):
for m in range(M+1):
if m - V[n] >= 0:
dp[n+1][m-V[n]] = max(dp[n][m], dp[n+1][m-V[n]])
if m + V[n] <= M:
dp[n+1][m+V[n]] = max(dp[n][m], dp[n+1][m+V[n]])
max_volum = -1
for m in range(M,-1,-1):
if max_volum < dp[N][m]:
print(m)
exit()
print(-1)