[백준 16194] 카드 구매하기 2- python (solved.ac - 실버 1)

https://www.acmicpc.net/problem/16194

16194번: 카드 구매하기 2

풀이

문제를 보았을때 알수있는 힌트

1개 샀을때 부터 n개를 살때까지 최소가 되는 값을 찾기위해서는 dp 형식으로 최소값을 찾는 것이 효율적이다. 

예시 4번을 예로 들어서 풀어보면

10
5 10 11 12 13 30 35 40 45 47

맨 처음 1개를 살때 최소로 사는 방법은 5 하나밖에 없다.

dp에는 1번째에는 5가 쌓일것이고 다음 2개를 살때 최소를 구해보면

10원으로 2개를 사거나 최소인 1개(5)를 2개 사는 방법이 있다. 아무튼 최소는 10이 된다.

다시 3개를 살때 최소는 3개인 11, 최소로 샀던 2개+최소로 산 1개=10+5=15 개를 살수있는데 이때 최소는 11이 된다.

이렇게 최소를 찾아가는 식을 작성하면 dp는 

[0, 5, 10, 11, 12, 13, 30, 35, 40, 45, 47]
[0, 5, 10, 11, 12, 13, 30, 35, 40, 45, 47]
[0, 5, 10, 11, 12, 13, 30, 35, 40, 45, 47]
[0, 5, 10, 11, 12, 13, 30, 35, 40, 45, 47]
[0, 5, 10, 11, 12, 13, 30, 35, 40, 45, 47]
[0, 5, 10, 11, 12, 13, 18, 35, 40, 45, 47]
[0, 5, 10, 11, 12, 13, 18, 23, 40, 45, 47]
[0, 5, 10, 11, 12, 13, 18, 23, 24, 45, 47]
[0, 5, 10, 11, 12, 13, 18, 23, 24, 25, 47]
[0, 5, 10, 11, 12, 13, 18, 23, 24, 25, 26]

이런식으로 쌓이게 될것이다. 이후 마지막에 26이 출력되게 하면 끝이나는 문제이다.

 

import sys
input = sys.stdin.readline

n=int(input())

list_n=[0]+list(map(int,input().split()))
dp=list_n[::]


for i in range(1,n+1):
    for j in range(1,i+1):
        dp[i] = min(dp[i],dp[i-j]+list_n[j])
        # print(dp)
    # print("")

print(dp[n])

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon16194.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리