[BOJ/GoldIII] 1943. 동전 분배 - JAVA 자바

• 252ms
• DP

동전은 쪼갤 수 없으므로 0/1 Knapsack 문제로 DP를 이용하여 해결할 수 있다.

 

입력받은 돈의 합(sum)을 구한 뒤, sum 이 홀수이면 반으로 나누지 못하므로 0 출력. 짝수이면 mid = sum / 2의 값을 동전들로 표현할 수 있는지 확인하면 된다.

dp[i][x] : i번째 동전을 사용할 때, x원을 표현하기 위해 사용한 동전의 최소 개수

 

먼저 사용한 동전의 최소 개수를 구할 것으로 모든 값들을 INF 로 초기화 해준다.

 

i번째 동전으로 x원을 만들 수 있을 때, 사용한 동전의 개수를 저장하고, i+1번째 동전으로 x원을 만드는 dp[i+1][x] 을 0으로 만들어준다. 그렇게 하면 dp 값이 INF 이면 pass , INF가 아니라면 이전 동전 index에서 x원을 만들 수 있는 것을 의미하므로 x원에서 i번째 동전을 사용하여 얼마를 만들 수 있는지 && 사용한 동전의 개수가 주어진 동전보다 작은지 체크해주며 갱신해준다.

 

예제 3번의 dp 테이블을 그려보자. 먼저 돈의 합은 6원으로 mid = 3 이 된다.

dp[0][0] 은 만들 수 있는 경우가 없으므로 0 이다.

	0	1	2	3
0 (1원 1개)	0	INF	INF	INF
1 (2원 1개)	INF	INF	INF	INF
2 (3원 1개)	INF	INF	INF	INF
3	INF	INF	INF	INF

dp[0][0] 에서 1원 1개로 1원을 만들 수 있으므로 dp[0][1] = 1 이 된다. 이 후 다음 동전에게 1원은 만들었다는 것을 남겨주기 위해 dp[1][1] = 0 으로 만들어준다.

	0	1	2	3
0 (1원 1개)	0	1	INF	INF
1 (2원 1개)	INF	0	INF	INF
2 (3원 1개)	INF	INF	INF	INF
3	INF	INF	INF	INF

dp[1][1] 에서 2원 1개가 있으므로 dp[1][1 + 2] = dp[1][3] = 1 이 된다. 다음 동전에게 1원은 만들었다는 것을 남겨주기 위해 dp[1][1] = 0 으로 만들어준다.

	0	1	2	3
0 (1원 1개)	0	1	INF	INF
1 (2원 1개)	INF	0	INF	1
2 (3원 1개)	INF	0	INF	0
3	INF	0	INF	0

dp[2][1] 과 dp[2][3] 에서 3원을 더하면 mid 값(3)을 초과하므로 다음 동전만 0 으로 만들어준 후 반복문이 종료된다.
최종적으로, dp[3][3] 값이 0 이므로 동전들로 3원을 만들 수 있다는 의미이다. 따라서 답은 1이 된다.

 

i번째 동전을 사용하면서 x 원을 만들 수 있다면, 다음 동전에게 x원은 내가 만들 수 있으니 여기서부터 너의 동전 금액으로 만들어봐 라는 플래그를 남겨줘야 한다.

 

따라서 x의 값이 i번째 동전에 의해 갱신되면 dp[i+1][x] = 0으로 두면 아 x는 이미 다른 동전에 의해 만들 수가 있구나. 나는 그럼 여기서 내 금액을 더해서 x + coin[i]원을 만들어 다시 dp값을 갱신하자

 

따라서 dp값이 INF가 아니면 dp[i+1][x]=0 을 갱신해주고 x원에서 i번째 동전금액을 더해 x + (i번째 동전금액) 원을 만들 수 있으면 dp[i][x+money]를 갱신하자.

 

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

public class Main {

    static int n, INF = Integer.MAX_VALUE;
    static int[][] coins;
    static int[][] dp;

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

        for (int t = 0; t < 3; t++) {
            n = Integer.parseInt(br.readLine());
            coins = new int[n][2];
            int sum = 0;

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                coins[i][0] = Integer.parseInt(st.nextToken());
                coins[i][1] = Integer.parseInt(st.nextToken());

                sum += coins[i][0] * coins[i][1];
            }

            if (sum % 2 == 1) {
                sb.append(0).append('\n');
                continue;
            }

            int mid = sum / 2;
            dp = new int[n + 1][mid + 1]; // i번째 동전으로 0부터 ~ mid 까지 만들 수 있는지

            for (int[] cols : dp)
                Arrays.fill(cols, INF );

            dp[0][0] = 0;

            for (int i = 0; i < n; i++) {
                int[] coin = coins[i];
                for (int j = 0; j <= mid; j++) {
                    if (dp[i][j] == INF )
                        continue;
                     // j원에서 i번째 동전을 더한 값이 mid 보다 작고 && i번째 동전의 개수보다 사용한 동전의 개수가 작을 때
                    if (j + coin[0] <= mid && dp[i][j] < coin[1])
                        dp[i][j + coin[0]] = Math.min(dp[i][j + coin[0]], dp[i][j] + 1);
                    dp[i + 1][j] = 0; // 다음 동전의 dp값은 0으로 
                }
            }
            if (dp[n][mid] == 0)
                sb.append(1);
            else
                sb.append(0);
            sb.append('\n');
        }
        System.out.println(sb);
    }

}

 

1차원 dp배열로도 구현할 수 있다.

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

public class Main {

    static int n;
    static int[][] coins;
    static int[] dp;

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

        for (int t = 0; t < 3; t++) {
            n = Integer.parseInt(br.readLine());
            coins = new int[n][2];
            int sum = 0;

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                coins[i][0] = Integer.parseInt(st.nextToken());
                coins[i][1] = Integer.parseInt(st.nextToken());

                sum += coins[i][0] * coins[i][1];
            }

            if (sum % 2 == 1) {
                sb.append(0).append('\n');
                continue;
            }

            // dp
            int mid = sum / 2;
            dp = new int[mid + 1]; // i번째 동전으로 0부터 ~ mid 까지 만들 수 있는지

            Arrays.fill(dp, Integer.MAX_VALUE);

            dp[0] = 0;

            for (int i = 0; i < n; i++) {
                int[] coin = coins[i];
                for (int j = 0; j <= mid; j++) {
                    if (dp[j] == Integer.MAX_VALUE)
                        continue;
                    if (j + coin[0] <= mid && dp[j] < coin[1])
                        dp[j + coin[0]] = Math.min(dp[j + coin[0]], dp[j] + 1);
                    dp[j] = 0;
                }
            }
            if (dp[mid] == 0)
                sb.append(1);
            else
                sb.append(0);
            sb.append('\n');
        }
        System.out.println(sb);
    }

}

```