1495번: 기타리스트 (DP) - Fastcampus

www.acmicpc.net/problem/1495

1495번: 기타리스트

# dp[i][j] = i번째 노래일때 j볼륨이 연주 가능한지 여부
#
# data = [5, 3, 7]
#
#            j=0  1  2  3  4  5  6  7  8  9  10 (볼륨)
#              0  0  0  0  0  1  0  0  0  0  0
# i=1 (1번곡)  1  0  0  0  0  0  0  0  0  0  1
# i=2 (2번곡)  0  0  0  1  0  0  0  1  0  0  0
# i=3 (3번곡)  1  0  0  0  0  0  0  0  0  0  1

def run(N, S, M, a):
    dp = [[0] * (M+1) for _ in range(N+1)]
    dp[0][S] = 1
    a = [0] + a  # dp와 a 인덱스 동일하게 맞추기

    for i in range(1, N+1):
        diff = a[i]
        for j in range(0, M+1):
            if dp[i-1][j] == 1:
                if j + diff <= M:
                    dp[i][j + diff] = 1
                if j - diff >= 0:
                    dp[i][j - diff] = 1

    volumns = [i for i, v in enumerate(dp[N]) if v == 1]
    return max(volumns) if volumns else -1


N, S, M = map(int, input().split())
data = list(map(int, input().split()))
print(run(N, S, M, data))