[백준 2294] 동전 2 - python (solved.ac - 골드 5)

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

2294번: 동전 2

풀이

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

문제 자체가 짧지만 단순하게 풀면 어렵고 다이나믹 프로그래밍으로 풀면 그나마 쉽게 풀 수 있는 문제이다.

처음에 풀 때, 반복문, 재귀를 이용해야하나 고민했는데 그러면 너무 많은 시간이 걸릴 것 같아서 포기했다.

그래서 dp로 10001이 담긴 리스트를 생성하고 가치가 낮은 동전을 넣고 그다음으로 가치 높은 동전을 넣어가면서 문제를 풀었다.

처음 동전 가치가 1이였다가 5로 변경되면 5번째 위치부터 가치를 1로 두고 dp를 증가하는 식으로 계산한다.

마지막에는 10001이 나온다면 만들 수 없는 수이기 때문에 -1이 나오게 한다.

import sys

input = sys.stdin.readline

n,k = map(int,input().split())
n_list = []
dp = [10001]*(k+1)
for i in range(n):
    n_list.append(int(input()))
n_list.sort()
dp[0]=0

for j in n_list:
    for i in range(j,k+1):
        dp[i]= min(dp[i],dp[i-j]+1)

if dp[-1]==10001:
    print(-1)
else:
    print(dp[-1])

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

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