백준(1495) - 기타리스트 Python
백준(1495) - 기타리스트
문제풀이 : DP 알고리즘, 파이썬
해결방법
처음엔 bfs로 풀면 될 줄알았으나, 오류가 발생했고 dp로 풀어야 한다는 것을 깨달았다.
- 전체 크기를 False로 초기화 시킨다.
- 첫째줄 strat 인덱스에 True 값을 넣는다.
- for문을 확인하면서 True 값인 경우 입력된 볼륨값을 조절할 수 있는 경우 다음 행 인덱스에 조절된 볼륨값에 True를 넣는다.
- 마지막 행을 순차적으로 확인하면서 True 값이 있으면 결과값에 넣는다.(큰 값이 결과적으로 들어오게 된다.)
예제
3 5 10
5 3 7
- DP 수행결과
# 기타리스트
import sys
input = sys.stdin.readline
n, start, max_v = map(int, input().split())
v = list(map(int, input().split()))
dp = []
for _ in range(n+1):
dp_arr = [False] * (max_v + 1)
dp.append(dp_arr)
dp[0][start] = True
for i in range(n):
for j in range(max_v+1):
check = dp[i][j]
if check:
if j + v[i] <= max_v:
dp[i+1][j+v[i]] = True
if j - v[i] >= 0:
dp[i+1][j-v[i]] = True
result = -1
for i in range(max_v+1):
if dp[n][i]:
result = i
print(result)
댓글남기기