[BOJ] 백준 2293 동전1 (JAVA)

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

2293번: 동전 1

 

🔍 Solve

dp배열을 사용해서 풀었습니다.

처음엔 점화식이 너무 안 보여서 공책에 합이 1부터 10까지 나올 수 있는 모든 경우의 수를 적어보았습니다.

dp의 기본적인 문제인 페인트칠하기와 규칙이 비슷해 보이는데 어떻게 풀 수 있을까 고민하다가

동전의 종류에따라 개수를 따로 세어주니 규칙을 찾을 수 있었습니다.

 

예제와 같이 동전의 종류가 1, 2, 5가 있습니다.

이 동전의 종류들을 담을 수 있는 coin배열을 만들어 담아줍니다. ( coin [] = {1, 2, 5} )

dp 배열은 K를 그대로 사용하기 위해 K+1의 크기만큼 선언해주었습니다.

주의할 점은, 만약 동전의 크기가 구하려고 하는 K보다 크다면 해당 동전으로 K를 만들 수 있는 경우가 없고, dp배열의 범위를 벗어나기 때문에 입력을 받을 때 예외처리를 해주어야 합니다.

 

우선 동전 1을 사용해서 각 가치의 합을 만들 수 있는 경우의 수를 넣어줍니다. 

 

다음으로 동전 1과 2를 사용해서 각 가치의 합을 만들 수 있는 경우의 수를 넣어줍니다.

기존 동전 1을 사용하여 넣어준 dp에 동전 2의 개수를 누적하여 합하여줍니다.

동전 2의 개수는 현재 자신의 가치에서 2를 뺀 가치의 dp값을 나타냅니다.

예를 들어 현재 가치가 5라면,

가치가 3일 때 모든 경우 : (1, 1, 1), (2, 1) 에 동전 2를 더하면

가치가 5일 때 모든 경우 : (1, 1, 1, 2), (2, 1, 2) 이므로, dp[5]의 2의 개수는 dp[3]입니다.

 

마지막으로 동전 1과 2, 5를 사용해서 각 가치의 합을 만들 수 있는 경우의 수를 넣어줍니다.

동전 5의 개수를 구할 때도, 현재 가치에서 5를 뺀 가치의 dp값을 사용합니다.

 

따라서 구할 수 있는 점화식은 dp[ i ] += dp[ i - coin[ c ] ]로 나타낼 수 있습니다.

답은 dp[K]를 출력합니다.

 

❗ Code

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

public class Main {

    static int N; //동전 종류
    static int K; //가치의 합
    static int[] coin;
    static int[] dp;

    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());

        coin = new int[N];
        dp = new int[K+1];
        for(int i=0;i<N;i++){
            int temp = Integer.parseInt(br.readLine());
            // 동전의 크기가 구하고자 하는 가치 K보다 작거나 같을때만 담아줌.
            if(temp<=K){
                coin[i] = temp;
            }
        }

        for(int c=0;c<coin.length;c++){
            int curCoin = coin[c];
            dp[curCoin] += 1;
            for(int i=curCoin+1;i<=K;i++){
                dp[i] += dp[i-curCoin];
            }
//            System.out.println(Arrays.toString(dp));
        }

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