백준(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)