백준 1943 동전 분배 (Java)

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

 

1. 문제

윤화와 준희는 솔선수범하여 쓰레기를 줍는 착한 일을 하였다. 원장선생님께서는 윤화와 준희를 칭찬하시고 과자나 사 먹으라고 하시며 동전 몇 개를 윤화와 준희에게 건네 주었다.

그런데 돈을 받은 윤화와 준희는 좋아하기보다 고민에 빠지고 말았다. 원장선생님께 받은 이 돈을 어떻게 나누어 할지 고민에 빠진 것이다. 두 사람 모두 상대방이 자기보다 1원이라도 더 받는 것은 도저히 인정할 수 없어 한다. 따라서 돈을 똑같이 둘로 나누어 가져야 두 사람이 모두 만족할 수 있게 된다.

하지만 두 사람에게 돈을 똑같이 나누는 것이 불가능한 경우도 있다. 예를 들어 500원짜리 1개와 50원짜리 1개를 받았다면, 이 돈을 두 사람이 똑같이 나누어 가질 수는 없다. 물론 동전을 반으로 잘라서 나누어 가질 수도 있겠지만 그러면 돈으로서의 가치를 잃기 때문에 그렇게 할 수는 없다.

이제 우리가 할 일은 다음과 같다. 원장 선생님께서 N가지 종류의 동전을 각각 몇 개씩 주셨을 때, 그 돈을 반으로 나눌 수 있는지 없는지 판단하는 것이다.

입력

세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다. 동전의 금액과 개수는 자연수이고, 같은 금액을 가진 동전이 두 번 이상 주어지는 경우는 없다.

출력

첫째 줄부터 세 줄에 걸쳐, 각 입력에 대하여 반으로 나누는 것이 가능하면 1, 불가능하면 0을 출력한다.

2. 풀이

각 테스트 케이스에 대해 주어진 동전을 정확히 2등분해야 한다. 즉, 한 사람에 대해 총 액수의 정확히 절반 만큼 줄 수 있다면 나머지 사람의 액수는 자연스레 같게 된다.

            for (int i = 0; i < n; i++) {
                tokenizer = new StringTokenizer(reader.readLine());

                //동전의 종류
                int price = Integer.parseInt(tokenizer.nextToken());
                //동전의 개수
                int amount = Integer.parseInt(tokenizer.nextToken());
                coin[i] = new Coin(price, amount);
                sum += price * amount;
            }

            if (sum % 2 == 1) {
                System.out.println(0);
                continue;
            }

우선 입력을 받고, 총 액수가 홀수일 경우 2등분이 불가능하므로 0을 출력한다.

            sum /= 2;
            dp = new boolean[n + 1][100001];
            dp[0][0] = true;

            //i번째 동전 사용
            for (int i = 1; i <= n; i++) {
                Coin cur = coin[i - 1];

                //각 액수를 보면서 이전 동전까지로 만들 수 있었던 액수인지 확인
                for (int j = 0; j <= sum; j++) {
                    if (dp[i - 1][j]) {

                        //가능하다면 해당 액수에 i번째 동전을 사용하여 새로운 액수 만들기
                        for (int k = 0; k <= cur.amount; k++) {
                            if (j + cur.price * k <= sum) {
                                dp[i][j + cur.price * k] = true;
                            }
                        }
                    }
                }
            }

            System.out.println(dp[n][sum] ? 1 : 0);

실질적 구현부이다. 가지고 있는 동전을 사용하여 총 액수의 절반을 나타낼 수 있는 지 확인하는 문제이므로, i개의 종류로 j원을 만들 수 있는 지 저장하는 2차원 dp 배열을 하나 선언해 주었다. 

 각 종류의 동전에 대해(i번째 종류 동전이라 가정), 0원부터 모든 액수까지 i-1번째까지의 동전으로 j원을 나타낼 수 있었다다면, 해당 액수에 i번째 액수를 가진 만큼(0개부터 k개까지) 분배하여 해당 액수를 참으로 바꾸어준다.

 

연산이 끝난 후 n종류의 동전을 가지고 sum(총 액수의 절반)을 나타낼 수 있다면 1, 아니라면 0을 출력해준다.

3. 코드 전문

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

public class Main {

    static int n;
    static Coin[] coin;


    //동전 개수, 동전 가치 -> 가능 여부
    static boolean[][] dp;


    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer;

        for (int test = 0; test < 3; test++) {
            n = Integer.parseInt(reader.readLine());

            coin = new Coin[n];

            int sum = 0;


            for (int i = 0; i < n; i++) {
                tokenizer = new StringTokenizer(reader.readLine());

                //동전의 종류
                int price = Integer.parseInt(tokenizer.nextToken());
                //동전의 개수
                int amount = Integer.parseInt(tokenizer.nextToken());
                coin[i] = new Coin(price, amount);
                sum += price * amount;
            }

            if (sum % 2 == 1) {
                System.out.println(0);
                continue;
            }

            sum /= 2;
            dp = new boolean[n + 1][100001];
            dp[0][0] = true;

            //i번째 동전 사용
            for (int i = 1; i <= n; i++) {
                Coin cur = coin[i - 1];

                //각 액수를 보면서 이전 동전까지로 만들 수 있었던 액수인지 확인
                for (int j = 0; j <= sum; j++) {
                    if (dp[i - 1][j]) {

                        //가능하다면 해당 액수에 i번째 동전을 사용하여 새로운 액수 만들기
                        for (int k = 0; k <= cur.amount; k++) {
                            if (j + cur.price * k <= sum) {
                                dp[i][j + cur.price * k] = true;
                            }
                        }
                    }
                }
            }

            System.out.println(dp[n][sum] ? 1 : 0);

        }


    }
}

class Coin {
    int price;
    int amount;

    public Coin(int price, int amount) {
        this.price = price;
        this.amount = amount;
    }
}