BOJ 1943 동전 분배

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

문제

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

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

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

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

---

입력

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

---

출력

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

---

예제 입력 1

2
500 1
50 1
3
100 2
50 1
10 5
3
1 1
2 1
3 1

예제 출력 1

0
1
1

---

코드

반례를 생각해내는 것도 문제 풀이에 있어 상당히 중요한 부분이기 때문에, 문제에서 주어진 예제도 문제 난이도에 영향을 미친다고 생각한다.

이번 문제를 읽고 예제를 봤을 때, 그리디로 풀면 바로 풀릴 것 같았지만, 이런 문제가 정말 조심해야 하는 문제인 것 같다.

문제의 예제만 보면 그리디로 풀어도 문제 없을 것 같지만, 5, 4, 3, 2, 2와 같은 경우는 그리디로 풀리지 않는다.

코딩 테스트는 시간도 중요하기 때문에, 문제를 처음 접할 때 예제만 보고 바로 풀이 방식을 결정한다면 큰 타격을 입을 수 있다.

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

public class Main {

    static class Coin {
        int value;
        int quantity;

        public Coin(int value, int quantity) {
            this.value = value;
            this.quantity = quantity;
        }
    }

    static int N;
    static int halfOfAmount; // 원장 선생님께서 주신 총액의 절반
    static Coin[] coins;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answers = new StringBuilder();
        int T = 3;
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            halfOfAmount = 0;
            coins = new Coin[N];

            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int value = Integer.parseInt(st.nextToken());
                int quantity = Integer.parseInt(st.nextToken());
                coins[i] = new Coin(value, quantity);
                halfOfAmount += value * quantity;
            }
            // 원장 선생님이 주신 총액이 홀수일 경우, 무조건 불가능
            if((halfOfAmount & 1) != 0) {
                answers.append('0').append('\n');
                continue;
            }

            // 총액의 절반을 저장 
            halfOfAmount >>= 1;

            char answer = splitAmount();
            answers.append(answer).append('\n');
        }

        System.out.println(answers);
    }

    static char splitAmount() {
        // 특정 금액을 만들 수 있는지 DP로 판단하기 위한 배열로 인덱스는 금액을 의미한다.
        boolean[] dp = new boolean[halfOfAmount + 1];
        dp[0] = true; // 맨 처음 상태가 0원이기 때문

        for (Coin coin: coins) {
            // dp 배열을 맨 끝부터 맨 처음까지 순회하며 검사
            for (int i = halfOfAmount; i >= 0; i--) {
                // 지금까지 검사한 코인으로 금액 i를 만들 수 있을 경우
                // 금액 i에 검사 중인 동전을 한 개씩 추가하며 만들 수 있는 금액을 체크
                if(dp[i]) {
                    int madeAmount = i;
                    for (int j = 1; j <= coin.quantity; j++) {
                        madeAmount += coin.value;

                        if(madeAmount > halfOfAmount) {
                            break;
                        }

                        dp[madeAmount] = true;
                    }
                }
            }
        }
        
        if(dp[halfOfAmount]) {
            return '1';
        }

        return '0';
    }
}