[백준] 1495번 기타리스트 (파이썬)

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

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(n):
    for j in range(m+1):
        if dp[i][j] == 1:
            num1 = j + v[i]
            num2 = j - v[i]
            if num1 <= m:
                dp[i+1][num1] = 1
            if num2 >= 0:
                dp[i+1][num2] = 1

result = -1
for i in range(m+1):
    if dp[n][i] == 1:
        result = i
print(result)