2624
-
백준 2624번 동전 바꿔주기 :: 마이구미알고리즘 풀이/동적계획법 2017. 11. 21. 20:18
이 글은 백준 알고리즘 문제 2624번 "동전 바꿔주기" 를 풀이한다.풀이 방법으로는 동적계획법을 통해 진행된다.문제 링크 - https://www.acmicpc.net/problem/2624 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 + 1×5 20 = 5×3 + 1×5입력으로 지폐의 금액 T, 동전..