[백준] 2293번 - 동전 1 [Java]

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

 

[백준] 2293번 - 동전 1 [Java]

---

1.  아이디어

 

무한 배낭 문제로 다이나믹 프로그래밍을 활용해서 해결할 수 있다.

---

2. 문제풀이

 

각 동전에 번호를 매긴 후 1번 동전만 주어졌을 때 사용해서 만들 수 있는 경우의 수, 1번, 2번 동전만 주어졌을 때 사용해서 만들 수 있는 경우의 수 이렇게 동전의 종류를 확장하며 풀어가면 된다. 다음 동전 종류가 주어졌을 때 기존의 조합으로도 각 경우를 만들 수 있으므로 해당 경우는 그대로 두고 새로운 동전으로 만들 수 있는 경우는 새로운 동전의 가치를 뺀 금액을 만들 수 있는 경우의 수로 찾으면 된다. 이때 같은 동전을 여러 개 사용할 수 있어서 새로운 동전이 주어진 상황에서의 금액과 비교해야한다.

---

3. 코드

 

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

public class Main_1D {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] coins = new int[1 + N];
        for (int i = 1; i <= N; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[1 + K];
        dp[0] = 1;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                if (j >= coins[i]) dp[j] += dp[j - coins[i]];
            }
        }

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

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

public class Main_2D {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] coins = new int[1 + N];
        for (int i = 1; i <= N; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        int[][] dp = new int[1 + N][1 + K];
        for (int i = 1; i <= N; i++) {
            dp[i][0] = 1;

            for (int j = 1; j <= K; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i]) dp[i][j] += dp[i][j - coins[i]];
            }
        }

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

---

4. 후기

 

- 1차원 dp

- 2차원 dp