[DP] 백준 1496번 : 기타리스트 - 파이썬 Python

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

1495번: 기타리스트

 

생각하기

N개의 연주곡

매번 곡이 시작하기 전에 볼륨을 바꾸고 연주

V[i] - i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨 (차이) 

-> P + V[i] 혹은 P - V[i] 로 연주 가능 이때, 0<= 볼륨 < M인 값이어야함

마지막 곡을 연주할 수 있는 볼륨중 최댓값은?

 

볼륨을 더하는 경우, 뺴는 경우를 모두 브루트포스 방식으로 푼다면 O(2^N)의 시간복잡도가 걸리게 된다

N이 최대 100인 경우 시간초과가 나게 된다 

 

• 모든 곡은 다 빠짐없이 연주가 되어야 함
• 모든 곡은 연주가 되어야하고 볼륨은 + / - 두가지 경우가 있음
• 이전에 연주한 곡들의 볼륨 data를 가지고 최대값을 쌓아나가야함

알아야 하는 것은 어떤 곡을 어떤 볼륨으로 연주할 수 있는지 없는지만 알면 됨

i번째 곡을 볼륨 j로 연주할 수 있는가...?

 

j는 0<=j <=1000

M이 10000이기 때문에 

i는 i번째 연주곡을 의미

범위에 제한이 있기 때문에 브루트포스로 만들지 않아도 값을 저장하며 해결 가능

 

dp[i][j] - i번째 곡을 연주시, j볼륨으로 연주가능한지에 대한 여부

 

시간복잡도

최대 곡의 개수가 50개, 가능항 볼륨이 최대 10000이므로

50 x 10000 형태의 배열을 dp로 풀어내는 것이기 때문에 시간복잡도 상에서의 문제는 없다

 

구현하기

초기값 - s 에서 시작한 V 값 + / -

dp[0][j] = True

j = s + V[0] / s - V[0]

 

dp[i][j] 는 dp[i-1][j-V[i]] 가 1인 경우 혹은 dp[i-1][j+V[i]]가 1인 경우 1

 

결론적으로 N * M 배열을 차례로 훑으면서

가장 마지막 i행을 for문 돌릴때 j의 최댓값을 구하면 되는 로직

 

주의해야할 점

N이 1인 경우에 처리를 꼭 해주어야 한다

N이 1인 경우 초기값 생성시 바로 최댓값을 판단하고 answer에 넣어주어야 함

 

 

N, S, M = map(int, input().split())

V = list(map(int, input().split()))

dp = [[False]*(M+1) for i in range(N)]

answer = -1

if 0<= S-V[0] <=M:
    dp[0][S-V[0]] = True
    if N-1 == 0:
        answer = max(answer, S-V[0])

if 0<= S+V[0] <=M:
    dp[0][S+V[0]] = True
    if N-1 == 0:
        answer = max(answer, S+V[0])


for i in range(1, N):
    for j in range(0, M+1):
        
        if 0<= j-V[i] <=M and dp[i-1][j-V[i]]:
            dp[i][j] = True
            if i== N-1:
                answer = max(answer, j)

        if 0<= j+V[i] <=M and dp[i-1][j+V[i]]:
            dp[i][j] = True
            if i== N-1:
                answer = max(answer, j)

print(answer)

 

다른 방법

위의 방법이 목표 연주곡에서 방법을 찾는 것이라면

아래의 방법은 목표 연주곡으로 방법을 찾는 것

N, S, M = map(int, input().split())

V = list(map(int, input().split()))
V.insert(0, -1)
dp = [[False]*(M+1) for i in range(N+1)]


dp[0][S] = True

answer = -1
for i in range(N):
    for j in range(M+1):
        if dp[i][j] is False:
            continue
    
        if 0<= j+V[i+1] <= M :
            dp[i+1][j+V[i+1]] = True
            if i == N-1:
                answer = max(answer, j+V[i+1])

        if 0<= j-V[i+1] <= M :
            dp[i+1][j-V[i+1]] = True
            if i == N-1:
                answer = max(answer, j-V[i+1])
        


print(answer)