[BOJ] 1943 - 동전 분배 JAVA

www.acmicpc.net/problem/1943

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

 

 

 

 

 

 

 

 

풀이 .

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

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

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

        int T = 3;
        while(T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            Coin[] coins = new Coin[n+1];  // 원장님이 주는 금액의 최대는 10만원
            boolean[] dp = new boolean[100001];  // i원 만들기 가능?

            int total = 0;
            for(int i = 1; i <= n; i++) {
                st = new StringTokenizer(br.readLine());
                int value = Integer.parseInt(st.nextToken());
                int quantity = Integer.parseInt(st.nextToken());
                coins[i] = new Coin(value, quantity);
                total += value * quantity;  // 받은 총 금액 구함
                for(int j = 1; j <= quantity; j++) {
                    dp[value * j] = true;  // 각 종류의 동전으로 만들 수 있는 액수 먼저 체크
                }
            }

            // 굳이 dp[] 다 안 채워도 되는 경우
            if(total % 2 == 1) {
                System.out.println(0);
                continue;
            }else if(dp[total / 2]) {
                System.out.println(1);
                continue;
            }

            // 주어진 동전으로 (total / 2)원을 만들 수 있는지 확인하면 될 듯?
            dp[0] = true;
            for(int i = 1; i <= n; i++) {
                int v = coins[i].value;
                int q = coins[i].quantity;

                for(int j = total/2; j >= v; j--) {
                    if(dp[j - v]) {  // dp[j-v]가 가능해야 거기에 동전 하나씩 더해서 다음 액수를 가능하게 만들지

                        // (j-v)원부터 동전 v를 하나씩 사용하는 것
                        for(int k = 1; k <= q; k++) {
                            if(j - v + v * k > total/2) break;  // dp[total/2] 이상으로는 어차피 채울 필요 없음
                            dp[j - v + v * k] = true;
                        }
//                        // 이게 이말임
//                        for(int k = 0; k < quantity; k++) {
//                            dp[j + value * k] = true;
//                        }
                    }
                }
            }
            System.out.println(dp[total / 2] ? 1 : 0);
        }
    }
}

 

DP로 푸는 냅색 문제.

 

동전을 하나씩 사용하여 total/2 ~ v에 대한 검사를 한다.

 

 

1. 0원까지 안 하고 v까지만 검사하는 이유? 

해당 동전을 1개만 사용해도 v-1원보다는 크니까

 

2. v~total/2가 아니라 total/2~v로 내려오면서 검사하는 이유?

냅색 문제에서 흔히 발생하는 오류를 피하기 위함.

오름차순으로 검사를 하면 이전에 이미 사용한 동전에 의해 true가 된 것을 가지고 동전을 또 사용해서 다음값을 true로 만든다.

결국 1원짜리 하나만 있어도 모든 dp[]가 true가 되어버린다.

이것을 막기 위해 큰 금액부터 검사.

 

3. if(dp[j - v]) 하는 이유?

v의 값을 가지는 동전 q개를 사용하려는 상황.

dp[j-v] 까지는 완성이 되어있어야 동전 1~q개를 사용하면서 dp[j], dp[j+v], ... , dp[j + (q-1)v]을 만들 수 있다.

 

 

 

 

dp 테이블에 대한 정의도 어려웠고 채우는 것도 어려웠다.

 

그냥 다 어려웠다..