백준 1495번 기타리스트

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

1495번: 기타리스트

다이나믹 프로그래밍으로 해결이 가능한 문제이며 또한 탐색해야되는 범위가 적기 때문에 2중 for문으로도 해결이 가능한 문제이다.

볼륨을 변경해야하는 단계마다 어떠한 볼륨으로 변경이 가능한지를 dp matrix에 저장을 해놓고 모든 경우의 수를 계산하해주면 된다.

 

문제의 예제 1번은

3 5 10
5 3 7

 

아래와 같은 형태로 dp matrix의 이전의 상태를 기록해주게 된다.

[[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
 [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]

최종 정답은 dp maxrix의 마지막 row에서의 최대값인 10이다.

 

 

* 전체코드

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 idx, each in enumerate(volume):
    for idx2, k in enumerate(dp[idx]):
        if k:
            upper = idx2 + each
            lower = idx2 - each

            if upper <= m:
                dp[idx+1][upper] = 1

            if lower >= 0:
                dp[idx+1][lower] = 1

max_value = -1
for idx, each in enumerate(dp[n]):
    if each:
        if idx > max_value:
            max_value = idx

print(max_value)