[백준] Gold V. 동전 1

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

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

4 MB

66085

31277

23859

47.364%

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

 

 

 

사용 알고리즘 

• 다이나믹 프로그래밍

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
    테이블: d[i]: i원을 만드는데 필요한 경우의 수
    점화식: d[i] = d[i] + d[i - coin]
 */
public class Main2 {
    static int n, k;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        int[] coins = new int[n];
        int[] d = new int[k+1];
        for(int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        d[0] = 1;
        for(int coin : coins) {
            for(int j = 1; j <= k; j++) {
                if (j - coin >= 0)
                    d[j] = d[j - coin] + d[j]; // dp[6] = dp[4] + dp[6]
            }
        }
        System.out.println(d[k]);
    }
}

 

 

회고

 

점화식을 세우는 과정이 쉽지 않았다. 다른 사람의 답을 참고하고 나니 한번에 이해가 되었다. 

3 10
1
2
5

 

동전이 1,2,5가 주어지고 합이 10을 만들어야 할 때,

1. 1원짜리 동전으로 1부터 10까지 만들 수 있는 경우의 수를 구한다.

2. 2원짜리 동전으로 1부터 10까지 만들 수 있는 경우의 수를 구한다 (이 때, 1원 경우의 수를 더해준다.)

3. 5원짜리 동전으로 5부터 10까지 만들 수 있는 경우의 수를 구한다. (이 때, 2원 경우의 수를 더해준다.)

 

d[i] = d[i] + d[i-coin]을 했을 때, d[i]는 기존에 구했던 경우의 수를 더해주면 된다.

쉬운 문제지만, 아이디어를 떠올리기 힘들었던 문제였다. 1,2,3 더하기 다시 풀어보자.