[ 백준 15989 해설 ] ( python ) 기타리스트
📚 기타리스트
문제
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 ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.
출력
첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.
예제 입력 1 복사
3 5 10
5 3 7
예제 출력 1 복사
10
예제 입력 2 복사
4 8 20
15 2 9 10
예제 출력 2 복사
-1
예제 입력 3 복사
14 40 243
74 39 127 95 63 140 99 96 154 18 137 162 14 88
예제 출력 3 복사
238
✍ 접근
- DFS 😖
- dp 1차원 배열 😖
- dp 2차원 배열 🤩
틀린코드(시간초과)
import sys
input = sys.stdin.readline
N,S,M = map(int,input().split())
volums = list(map(int,input().split()))
res = -1
def DFS(L,vol):
global res
if L == N:
if 0<=vol<=M:
res = max(res,vol)
return
if 0<=vol<=M:
DFS(L+1,vol+volums[L])
DFS(L+1,vol-volums[L])
DFS(0,S)
print(res)해설
DFS를 이용해서 돌리려고 했는데 시간초과가 나왔다.
당연. 방문한 노드조차 고려해주지 않았다.
틀린코드(틀렸습니다)
import sys
input = sys.stdin.readline
N,S,M = map(int,input().split())
volums = list(map(int,input().split()))
dp = [-1]*(M+1)
dp[S] = 0
for i in range(N):
for j in range(M+1):
if dp[j] == i:
if 0 < j - volums[i] <=M:
dp[j-volums[i]] = dp[j]+1
if 0<j+volums[i] <=M:
dp[j+volums[i]] = dp[j]+1
for i in range(M,-1,-1):
if dp[i] == N:
print(i)
break
else:
print(-1)해설
볼륨만큼의 개수를 가진 1차원 배열 dp에 그 볼륨에서 연주되는 음악을 저장해준다.
맨 마지막 N번째 재생되는 음악이 마지막에 연주하는 음악.
완성된 dp를 끝에서부터 0까지 돌면서 N을 찾아서
있으면 i(음량)
없으면 -1
을 출력해준다
틀린 이유 : 1차원 배열에서 두 if문을 돌면서 초기화될것을 고려하지 못했음
정답코드
import sys
input = sys.stdin.readline
N,S,M = map(int,input().split())
volums = list(map(int,input().split()))
dp = [[0]*(M+1) for _ in range(N+1)]
dp[0][S] = 1
for i in range(N):
for j in range(M+1):
if dp[i][j] == 1:
if 0 <= j - volums[i] <=M:
dp[i+1][j-volums[i]] = 1
if 0<=j+volums[i] <=M:
dp[i+1][j+volums[i]] = 1
for i in range(M,-1,-1):
if dp[N][i] == 1:
print(i)
break
else:
print(-1)해설
dp를 2차원 배열로 만들어서 세로는 음악 / 가로는 음량 크기를 준다
하위 내용은 위 코드와 같다
⭐ 배움
- dp... dp..!!.. . . . . .dp!!!!!!!!!!!!!!!