[BOJ] Q1890 점프

[BOJ] Q1495 기타리스트

Question

Language: Python

Difficulty: Silver 1

Example

N,S,M=3,5,10
Volume_List=[5,3,7]

처음에 시작하는 볼륨은 5이다, 1번째 곡을 연주하면서 기타리스트는 5만큼의 볼륨 변화를 줄 수 있다. 이렇게 되면 5-5=0,5+5=10으로 첫번째 곡에서 줄 수 있는 볼륨값은 0,10이다.

이런식으로 각각의 곡들을 연주할 떄 쓰이는 볼륨을 구하기 위해 이전에 줄 수 있었던 볼륨값들에 볼륨 변화량을 주어서 구한다.

volume[i-1][j]였으면 volumne[i][j-change],volume[i][j+change]로 연주할 수 있다. 주어진 조건에서 볼륨을 조절할 수 없는 경우가 있을 수도 있으니 이에 대한 예외처리를 생각해야한다.

Solution

def solution():
    dp=[[-1] * (max_volume+1) for _ in range(n+1)]
    dp[0][start]=0

    for i in range(n):
        check=False
        for volume in range(max_volume+1):
            if dp[i][volume]==-1:
                continue
            check=True
            if (volume + volumes[i]) <= max_volume:
                dp[i+1][volume+volumes[i]]=0
            if (volume - volumes[i]) >=0:
                dp[i+1][volume-volumes[i]]=0
        #중간에 볼륨 조절을 할 수 없는 경우 빠져나온다.
        if not check:
            break
  
    answer=-1
    for volume in range(max_volume+1):
        if dp[n][volume] !=-1:
            answer=volume
    return answer
  
if __name__ == "__main__":
    n,start,max_volume=map(int,input().split())
    volumes=list(map(int,input().split()))
    print(solution())