📖 [백준알고리즘 풀이] Q.2293 동전 1 문제 풀이 - java

📖 문제

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

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.

그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

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

🔍 접근법

동전 문제입니다.

동전 문제는 그리디 유형으로도 접근할 수 있습니다.

하지만,

이번 동전 1 문제 같은 경우에는

주어지는 동전의 가치가 배수 관계로 이뤄지지 않고

모두 임의로 주어지기 때문에 그리디 알고리즘으로 풀이하기에 알맞지 않습니다.

대신 동적 프로그래밍 방식으로 풀이 할 수 있습니다.

동전의 개수는 무한정으로 사용이 가능하니

각 동전으로 만들 수 있는 모든 경우의 수를 동적 프로그래밍을 통해 알맞게 구할 수 있습니다.

1원부터 i원까지 각 동전으로 만들 수 있는 경우에 대한 점화식은

dp[i] = d[i-coin]+1 입니다.

i원 까지의 모든 경우의 수 = (i-coin)원 까지의 모든 경우의 수 + 1 입니다.

i-coin원에서 coin 동전을 더해 i원을 만들 수 있기 때문입니다.

이를 이용해 n개의 동전으로 각각의 동전을 더해 i원을 만들 수 있는 경우를 더해나가면 답을 구할 수 있습니다.

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

또한 각 동전에 대한 반복문을 선택 된 동전 가치부터 시작하여 중복을 방지 할 수 있습니다.

💻 코드

package problem.dynamic;

import java.io.*;

public class Main_2293 {
    static int n;
    static int k;
    static int dp[];
    static int coin[];
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        solve();
        bw.flush();
        bw.close();
    }
    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input[] = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);
        coin = new int[n];
        dp = new int[k+1];
        for(int i=0; i<n; i++){
            coin[i] = Integer.parseInt(br.readLine());
        }
        br.close();
    }
    public static void solve() {
        dp[0] = 1;
        for (int i = 0; i <n; i++) {
            for (int j = coin[i]; j <= k; j++) {
                dp[j] += dp[j-coin[i]];
            }
        }
        System.out.println(dp[k]);
    }

}

Written on February 15, 2021