[BOJ][python] 1495. 기타리스트

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

1495번: 기타리스트

---

💡IDEA

동적 계획법을 사용하는 문제이다.

시작 볼륨에서부터 시작해서 조절할 수 있는 크기만큼 더하고 뺀 값을 바탕으로 dp 배열을 채운다.

예제 입력 1번의 경우는 다음과 같다.

예제 입력 1 dp

S=5에서부터 시작해서 볼륨리스트 첫번째 값인 5를 더하고 뺀 값인 0과 10을 체크해준다.

볼륨리스트 두번째 값은 3인데, 0에서는 3으로, 10에서는 7로 체크할 수 있다. 범위가 0과 M 사이임을 주의한다.

볼륨리스트 세번째 값은 7이고, 3에서는 10으로, 7에서는 0으로 체크할 수 있다.

즉, dp를 이차원 배열로 만들어 이전 행의 값을 사용하는 방식으로 풀 수 있다.

마지막 N행에서는 1로 체크되어있는 값들 중 인덱스값이 가장 큰 값을 출력한다. 만약 1이 하나도 없다면 -1을 출력한다.

 

📌CODE

import sys
input = sys.stdin.readline

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

for i in range(M, -1, -1):
    if dp[N][i]:
        print(i)
        break
else:
    print(-1)