백준 알고리즘 1495번 기타리스트 - 파이썬

www.acmicpc.net/problem/1495

1495번: 기타리스트

DP를 공부하던 중 기타가 취미인 나에게 딱 꽂히는 문제 제목이 보여서 바로 들어갔다. 하지만... 시간 엄청 쓰고 결국 다른 사람 풀이를 참고해 풀었다....

DP를 접할 때마다 나의 멍청함을 매번 느끼게 된다. DP 테이블을 1차원 배열로 선언해서 단순하게 max 값만 취하고 조건만 잘걸어주면 풀릴 줄 알았으나 완전 잘못된 접근이었다. 

결국 다른 사람의 코드를 참고해 DP테이블을 이차원 배열로 만들고 각 곡에 대해 0 <= 현재 볼륨 <= M 의 범위 까지 가능한 지 탐색해야 하는 문제였다. 이와 비슷한 문제로 knapsack problem이 있다는데 다음 문제로 이 문제를 풀어보면서 다시 DP를 학습해야 할 것 같다.

n, s, m = map(int, input().split())
v = list(map(int, input().split()))

dp = [[False] * (m + 1) for _ in range(n + 1)]
dp[0][s] = True

for i in range(n):
    for j in range(m + 1):
        if not dp[i][j]:
            continue
        if j + v[i] <= m:
            dp[i + 1][j + v[i]] = True
        if j - v[i] >= 0:
            dp[i + 1][j - v[i]] = True

answer = -1
for i in range(m, -1, -1):
    if dp[n][i]:
        answer = i
        break

print(answer)