[알고리즘/백준] 1495번 : 기타리스트(python)

처음에 백트래킹으로 풀었다가 틀렸다...
곡과 점수로 dp 리스트를 만들어야 한다.
각 곡별로 0 ~ M까지의 점수를 받을 수 있기 때문에 리스트를 만들고 0으로 초기화한다.
처음은 dp[0][S]이다. 왜냐하면 맨 처음에 S로 시작하기 때문이다.
dp[i-1][j] == 1이면 계산을 해준다.

리스트가 다 채워지면 맨 마지막줄을 for문으로 돌면서 1이면 출력해준다.

N, S, M = map(int, input().split())
a = 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] == 1:
            if j+a[i - 1] <= M:
                dp[i][j + a[i - 1]] = 1
            if j - a[i - 1] >= 0:
                dp[i][j - a[i - 1]] = 1
for i in range(M, -1, -1):
    if dp[N][i] == 1:
        print(i)
        exit()
print(-1)