[백준/1495/파이썬] 기타리스트

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

1495번: 기타리스트

Problem

• 곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 

조건 

모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

SOL

분기점이 계속 2가지 경우의 수로 갈라지는 문제기 때문에, 재귀적으로 구현도 가능하다.

모든 볼륨에 대해서, 연주 가능여부를 check 해준다. 왜냐하면, 줄였다가 나중에 크게하는게 더 이득일 수도있기 때문.

그래서, DP table도 최대 M까지 , 한 loop 마다 기록을 해주는 방식으로 구현 하였음.

 

import sys
input = sys.stdin.readline
N,S,M = map(int,input().split())
vol = list(map(int,input().split()))
#모든 볼륨에 대해서, 연주 가능여부를 check 해준다.
#왜냐하면, 줄였다가 나중에 크게하는게 더 이득일 수도있기 때문.
#그래서, DP table도 최대 M까지 , 한 loop 마다 기록을 해주는 방식으로 구현 하였음.
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] ==0: #이전걸 기준으로 탐색
            continue
        # DP[i-1][j] ==1이면, 실행
        if j+vol[i-1]<=M:
            DP[i][j+vol[i-1]] = 1
        if j-vol[i-1]>=0:
            DP[i][j-vol[i-1]] =1

ans=-1
for i in range(M,-1,-1):
    if DP[N][i]:
        ans=i
        break
print(ans)