[백준] [DP] 1495. 기타리스트

1495. 기타리스트

[백준/Python(파이썬)] 1495 기타리스트

 

• 다른 사람 풀이참고해서 다시 풀었을 때  error ㅡㅡ
  • 문제의 핵심 : 2차원배열을 사용
    • d[i][j] :i번째 곡을 j볼륨으로 만들 수 있는지 여부(1:가능/0:불가능)
  • #시작볼륨은 1번 곡 시작하기 전 볼륨 -> 0번째
  • i가 볼륨이기 때문에 뒤에서부터 가장 먼저 가능한 값이 최대볼륨
  • 📍가능하지 않을 경우의 출력 계속 빼먹는데 잘 확인하기

 

• 에러 발생 이유: 이전 곡의 j 볼륨이 가능했을 때 다음 곡 볼륨 범위 탐색해야하는데
• 이전곡 j 볼륨의 가능 유무를 확인하지 않음!

#곡 시작 전 볼륨 수정
#볼륨 v[i]: i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨  (+.-)
#0 이상 m이하 가능
#출력: 마지막 곡의 볼륨 중 최댓값
import sys
input=sys.stdin.readline


#곡 개수 n / 시작볼륨 s / 제한 m
n,s,m=map(int,input().split())
V=list(map(int,input().split()))
result=[]

#d[i][j] : i번째 곡에서 j볼륨이 가능한지 여부 : 1:가능/ 0: 불가능
#시작볼륨은 1번 곡 시작하기 전 볼륨 -> 0번째
d=[[0 for _ in range(m+1)] for _ in range(n+1)]
d[0][s]=1 #0번째 시작볼륨 

#1번부터 n번곡
for i in range(1,n+1):
    for j in range(m+1):
        if 0<=j+V[i-1]<=m:
            d[i][j+V[i-1]]=1
        if 0<=j-V[i-1]<=m:
            d[i][j-V[i-1]]=1

#마지막 곡에 가능한 볼륨 없으면 -1
answer=-1
#i가 볼륨이기 때문에 뒤에서부터 가장 먼저 가능한 값이 최대볼륨
for i in range(m,-1,-1):
    if d[n][i]==1: 
        answer=i
        break

print(answer)

 

• 빠진 부분 추가

#곡 시작 전 볼륨 수정
#볼륨 v[i]: i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨  (+.-)
#0 이상 m이하 가능
#출력: 마지막 곡의 볼륨 중 최댓값
import sys
input=sys.stdin.readline


#곡 개수 n / 시작볼륨 s / 제한 m
n,s,m=map(int,input().split())
V=list(map(int,input().split()))
result=[]

#d[i][j] : i번째 곡에서 j볼륨이 가능한지 여부 : 1:가능/ 0: 불가능
#시작볼륨은 1번 곡 시작하기 전 볼륨 -> 0번째
d=[[0 for _ in range(m+1)] for _ in range(n+1)]
d[0][s]=1 #0번째 시작볼륨 

#1번부터 n번곡
for i in range(1,n+1):
    for j in range(m+1):
        if d[i-1][j]==1: #빠진부분
            if 0<=j+V[i-1]<=m:
                d[i][j+V[i-1]]=1
            if 0<=j-V[i-1]<=m:
                d[i][j-V[i-1]]=1
    
#마지막 곡에 가능한 볼륨 없으면 -1
answer=-1
#i가 볼륨이기 때문에 뒤에서부터 가장 먼저 가능한 값이 최대볼륨
for i in range(m,-1,-1):
    if d[n][i]==1: 
        answer=i
        break

print(answer)