백준 2293. 동전1
16 Aug 2021문제 바로가기
문제 요약
n가지 종류의 동전이 무한대로 있다고 할 때, k 금액이 되도록 만들 수 있는 동전의 경우의 수를 구하는 문제이다. 이때, 사용하는 동전의 구성이 동일하다면 한 가지 경우로 취급한다.
문제 풀이 포인트
간단한 경우의 수 DP 문제지만 한 가지 주의해야할 점이 있다. 먼저 DP의 점화식을 세워보자면,
i원을 만들 수 있는 방법의 수는 i원에서 동전의 금액을 뺀 경우의 수의 합과 동일하다.
문제에 있는 예시인 1, 2, 5원 동전과 k=10 를 활용해보자면
i원을 만들 수 있는 경우의 수는 (i-1원을 만들 수 있는 경우의 수) + (i-2원을 만들 수 있는 경우의 수) + (i-5)원을 만들 수 있는 경우의 수 라는 것이다.
또한, 점화식의 기저조건을 찾아보자면 dp[0] = 1이라는 점이다. dp[0] = 1인 이유는 0원을 만들기 위한 방법은 아무 동전도 선택하지 않는 방법 1개가 있기 때문이다.
마지막으로 주의해야할 사항으로 중복을 허용하지 않는 점을 들 수 있다. 코드를 짜다보면
- 1원부터 k원까지 각각 동전 종류를 순서대로 체크하는 방법
- 각 동전 종류별로 1원부터 k원까지 각각 체크해보는 방법 2가지 방법을 고민하게 될 수 있다. 본인은 1번 방법을 택했는데 이 방법의 경우 같은 동전 구성에서 중복이 발생할 수 있기 때문에 주의해야한다. 위의 1번은 아래 코드에서 주석으로 달아놓겠다.
문제 코드[JAVA]
코드 펼치기
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] coins = new int[n];
for (int i = 0; i < n; i++) {
coins[i] = sc.nextInt();
}
int[] dp = new int[k+1];
dp[0] = 1;
// 1번 방법
// for (int i = 1; i < k + 1; i++) {
// for (int j = 0; j < n; j++) {
// if(i - coins[j] >= 0){
// dp[i] += dp[i - coins[j]];
// }
// }
// }
// 2번 방법
for (int i = 0; i < n; i++) {
for (int j = 1; j < k+1; j++) {
if(j - coins[i] >= 0){
dp[j] += dp[j - coins[i]];
}
}
}
//System.out.println(Arrays.toString(dp));
System.out.println(dp[k]);
}
}