[BOJ] 기타리스트

---

코드

import sys
input = sys.stdin.readline

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:    # dp[i][j] = i번째 곡에 j볼륨을 설정 가능한지 여부
            # 볼륨을 늘리거나 줄일 수 있음
            num1 = j + v[i]
            num2 = j - v[i]
            # 설정 가능한 볼륨이면 가능으로 표시(1)
            if 0 <= num1 <= m:
                dp[i+1][num1] = 1
            if 0 <= num2 <= m:
                dp[i+1][num2] = 1
                
ans = -1
for i in range(m+1):
    # 마지막 곡: n
    if dp[n][i] == 1:
        ans = i
print(ans)

결과

풀이 방법

• 다이나믹 프로그래밍 문제이다.
• top down 방식으로 가능한 볼륨을 모두 추리는 방식으로 코드를 작성했으나 그러면 리스트에 최대 2^50개의 볼륨이 들어갈 수 있어서 메모리 초과가 났다
• DP를 활용해야 하는데, dp 배열을 어떻게 정의하느냐가 핵심이다.
• 볼륨 범위가 정해져 있으므로 dp를 n x m 배열로 선언하여 dp[i][j] = i번째 곡에 j볼륨을 설정 가능한지 여부로 표현한다
• 시작볼륨은 0번째 곡에 s볼륨이 설정 가능하다고 표시해 놓는다.
• 그리고 반복문으로 현재 볼륨에 v[i] 볼륨을 더하거나 빼서 다음 곡에서 설정 가능한 볼륨에 가능표시를 한다
• 정답을 구하려면 마지막 곡에서 설정 가능한 볼륨 중 최대값을 구하면 된다.

---