[백준] 1495 기타리스트 (Python)

1. 문제 조건

• 곡의 개수 N, 시작 볼륨 S, max 볼륨 M
• 매번 곡 연주를 시작하기 전에 볼륨 조정을 하는데 볼륨 조정이 가능한 값이 V리스트에 담겨있음
• ex) max 볼륨이 10, 시작 볼륨이 5, V[0]이 3이면 될 수 있는 볼륨 값은 2 or 8

 

2. 풀이 전 생각정리

• 볼륨 조정이 들어갈 때마다 가능한 볼륨의 가짓수는 2배로 늘어난다. 단 가능한 볼륨값 범위 안에 속하지 않은 옵션들은 없애줘야 한다.
• 볼륨 조정이 있을 때마다 가능한 볼륨의 크기를 담고, 다음 볼륨 조정이 있을 때 다시 확장시키는 방법?
• (N+1)*(M+1) 크기의 0으로 초기화된 리스트를 만들어 볼륨 조정을 하나씩 해가며 발생할 수 있는 경우를 1로 표시해놓기?

 

3. 메모리 초과 뜬 코드

• 볼륨 조정을 하기 전마다 가능한 볼륨 크기를 dp에 정수 형태로 담고
• 볼륨조정을 하며 기존의 볼륨을 조정하여 가능한 볼륨크기를 다시 dp에 정수 형태로 담기

N, S, M = map(int, input().split())
V = list(map(int, input().split()))
dp = []
dp.append(S)

for i in range(len(V)):
    temp_list = []
    while dp:
        temp_num = dp.pop()
        if 0<=temp_num+V[i]<=M:
            temp_list.append(temp_num+V[i])
        if 0<=temp_num-V[i]<=M:
            temp_list.append(temp_num-V[i])
    dp = temp_list
    
if len(dp)==0:
    print(-1)
else:
    print(max(dp))

 

4. 성공 코드

• (N+1)*(M+1) 이차원 리스트를 0으로 초기화한 뒤 볼륨 조정이 들어갈 때마다 가능한 옵션들을 1로 표기
• 행은 몇 번째 볼륨 조정 이후 결과인지를 뜻하고, 열은 가능한 볼륨을 뜻함
• ex) 0행에는 초기 볼륨 값의 열에만 1이 표기, 1행에는 첫 번째 볼륨 조정 이후 가능한 볼륨 크기를 의미하는 열들에만 1 표기

N, S, M = map(int, input().split())
V = list(map(int, input().split()))
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: #j가 음 높이
            if j + V[i-1]<=M:
                dp[i][j+V[i-1]] = 1
            if j - V[i-1]>=0:
                dp[i][j-V[i-1]] = 1

result = -1
for i in range(M,-1,-1):
    if dp[N][i]==1:
        result = i
        break

print(result)