백준 2624번 - 동전 바꿔주기
https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 필요한 배경지식 다이나믹 프로그래밍 문제 해결 방법 동전의 순서는 중요하지 않으므로 동전별로 차례대로 K원을 몇개나 만들 수 있는지 다이나믹 프로그래밍 하면 된다. 문제에서 주어진 입력으로 예를 들어보겠다. dp[K]를 'K원으로 만들 수 있는 동전조합의 수' 라고 할때 먼저 base case로 dp[0] = 1 을 정의할 수 있다. ('0원을 만들 수 있는 경우는 한가지'라고 인..
알고리즘 공부/문제풀이
2022. 1. 22. 03:00
반응형