백준 2293 동전 1

문제

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


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

---

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //N, K 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        //코인 입력 받기
        int[] coins=new int[n];
        for (int i = 0; i < n; i++)
            coins[i] = Integer.parseInt(br.readLine());

        //각 동전에 대해서 현재 해당 금액을 만들 수 있는 경우의 수에 +해주기
        int[] dp=new int[k+1];
        for(int coin:coins){
            if(coin>k)
                continue;

            dp[coin]+=1;

            for(int i=1; i+coin<=k; i++)
                dp[i+coin]+=dp[i];

        }

        System.out.println(dp[k]);
    }
}

---

해결 과정

1. 한 동전을 하나 사용하면 해당하는 금액을 만들 수 있는 경우의 수가 1 늘어난다. -> 어떤 금액을 만들 수 있을 때, 그 금액에 한 동전을 더한 금액을 만들 수 있는 경우의 수가 어떤 금액을 만들 수 있는 경우의 수만큼 늘어난다.

2. 😁