Python 백준 1495번 - 기타리스트 (메모리 초과 해결)

문제

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

입력

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

출력

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

내 생각

문제를 처음 보고 느꼈을때는, 그냥 백트래킹 문제인 줄 알았다. 왜냐하면 처음부터 시작해서 끝까지 볼륨이 바뀌는 것만 result 라는 결과에 담아서 max 값을 출력하면 되기 때문이다. 그리고 시간 초과를 줄이기 위해서 모든 leaf 까지 탐색하지는 않고, 중간에서 return 으로 불필요한 부분은 자르려는 생각이었다.

import sys
 
N, S, M = map(int, sys.stdin.readline().split())
V = list(map(int,sys.stdin.readline().split()))
current_volume_control = 0
result = []
 
def cal(index, value):
    global current_volume_control
    if value < 0 or value > M:
        return
 
    if index == N:
        if value not in result:
            result.append(value)
        return
 
    current_volume_control = V[index]
    cal(index + 1, value + current_volume_control)
    current_volume_control = V[index]
    cal(index + 1, value - current_volume_control)
 
cal(0, S)
print(max(result) if result else -1)
 
 
 

아, 메모리 초과가 떴다, 왜그럴까? 라고 생각을 좀하다가 질문창에 혹시 메모리 초과에 대한 Test Case 가 있을까 해서 찾아 보았다.

30 500 1000

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

를 입력하면 어떻게 될까? 아~주 비효율 적일 것이다. 문제점은 이를 트리로 표현해서 모든 리프를 찍는데, 재귀적으로 함수가 동작하다 보니 메모리가 터지는 현상이 발생하는 것이다. 또한 위와 같은 경우는 모든 경우가 다되는 경우인데 결과 result 에도 엄청난 결과들이 비효율적으로 찍힐 것이다.

 

해결책

이는 메모이 제이션(Memoization) 즉, DP(Dynamic Programming)로 해결할 수 있다.

우선, 최소부터 최대까지만 리스트의 길이로 잡을 수 있을 것이고, 각각의 볼륨 조절 마다 행에 T인지 F 인지 찍어주면 된다.

처음 배열을 잡는다. 그후, 초기 S 인덱스에만 T로 세팅한다. 각 번째(i)의 볼륨 조절을 따져서 해당 볼륨이 될 수 있는 지 없는 지 확인한다. 후에 마지막 볼륨 조절을 담당하는 부분에서 T인 부분의 인덱스 값을 출력하면 원하는 결과일 것이다.

import sys
 
N, S, M = map(int, sys.stdin.readline().split())
V = list(map(int,sys.stdin.readline().split()))
dp = [[False] * (M+1) for _ in range(N+1)]
dp[0][S] = True
result = []
for i in range(1, N+1):
    for j in range(M+1):
        if dp[i - 1][j] == False:
            continue
        if j - V[i-1] >= 0:
            dp[i][j - V[i-1]] = True
        if j + V[i -1] <= M:
            dp[i][j + V[i-1]] = True
 
for index, value in enumerate(dp[-1]):
    if value:
        result.append(index)
print(max(result) if result else -1)