[백준 JAVA] 1943번: 동전 분배

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

 

처음 접근은 뭔가 그리디하게 풀 수 있을 꺼같아서 그렇게 접근하고 문제를 풀었다.

 

1. 먼저 동전의 총 합이 홀수면 정확히 나눌 수 없으므로 무조건 0반환

 

 2. 그 다음은 주어진 동전들을 사용하여 총합의 절반인 값을 만들 수 있으면 정확히 반으로 나눌 수 있는 것이므로 이것을 그리디하게 가치가 높은 동전부터 꺼내서 해결하였다.

 

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

public class Main {
    public static int N, total;
    public static PriorityQueue<int[]> pq;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for(int TC = 0; TC < 3; TC++){
            N = Integer.parseInt(br.readLine());
            pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2[0], o1[0]));
            total = 0;
            for(int i = 0; i < N; i++){
                st = new StringTokenizer(br.readLine());
                int value = Integer.parseInt(st.nextToken());
                int count = Integer.parseInt(st.nextToken());
                pq.offer(new int[] {value, count});
                total += value * count;
            }

            if(total % 2 == 1) System.out.println(0);
            else System.out.println(isValid());
        }
    }
    public static int isValid(){
        total = total / 2;
        while(!pq.isEmpty() && total != 0){
            int[] cur = pq.poll();
            int value = cur[0];
            int count = cur[1];
//            System.out.println(value + " " + count + " " + total);

            if(value > total) return 0;
            while(count > 0 && total - value >= 0) {
                total -= value;
                count--;
            }
        }

        if(total == 0) return 1;
        else return 0;
    }
}

 

값을 처리할 수 없는 높은 가치가 나오는경우 무조건 0으로 반환하게끔 짰는데 이때 반례가 생겼다.

 

만약 동전이 [8, 7, 5, 4] 와 같이 주어진다면 13을 8과 5, 7과 4로 분배해야하는데 7이 나오는 순간 0으로 반환해버린다.

 

따라서 이 if(value > total) return 0; 줄을 지우고 다시 돌려도 실패가 되었다.

 

반례를 GPT 한테 물어보았고 다음과 같은 반례가 존재하였다.

 

[4, 4, 3, 3, 2, 2] 일경우 총합은 18이고 9를 만들어야 할 때 4 두개가 먼저 처리해버리므로 0을 리턴해버린다. 하지만 4, 3, 2 하나씩 사용할 경우 9를 만들 수 있으므로 틀리게 된다.

 

뭔가 처음 이 방법을 생각했을 때 반례가 생길것 같아 불안하긴 했는데 역시나 생겼다.

 

분배문제를 처음풀어본 영향도 있을것이라 생각한다. 이문제의 정해는 DP 이다.

 

아까 말한대로 총합의 절반을 만들 수 있으면 가능인데

 

각 동전을 몇개 쓸지 선택해야되고 몇개쓸지 선택할 때  그리디하게 큰 동전을 미리 채워버리면 작은 동전으로 채울 수 있는 경우를 따지지 못하게 되므로 가능한 합의 집합을 누적하는 DP로 풀어야 한다.

 

dp[j] 는 지금까지 본 동전들로 합 j 를 만들 수 있는가 ? 이고

boolean 배열로 가능 / 불가능만 알면된다.

 

하지만 java에서 boolean을 활용한 조건은 4bit 로 다시 환산해서 계산하므로 int 로 0일때는 불가능 1일때는 가능으로 생각하여 풀이하였다.

 

 

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

public class Main {
    public static int N, total;
    public static int[] value, count;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for(int TC = 0; TC < 3; TC++){
            N = Integer.parseInt(br.readLine());
            value = new int[N];
            count = new int[N];
            total = 0;
            for(int i = 0; i < N; i++){
                st = new StringTokenizer(br.readLine());
                value[i] = Integer.parseInt(st.nextToken());
                count[i] = Integer.parseInt(st.nextToken());
                total += value[i] * count[i];
            }

            if(total % 2 == 1) System.out.println(0);
            else System.out.println(isValid());
        }
    }
    public static int isValid(){
        int target = total / 2;
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for(int i = 0; i < N; i++){
            int v = value[i];
            int c = count[i];
            for(int k = 0; k < c; k++){
                for(int j = target; j >= v; j--){
                    if(dp[j - v] == 1) dp[j] = 1;
                }
            }
        }

        if(dp[target] == 1) return 1;
        else return 0;
    }
}

 

 

잘풀었다고 생각했는데 시간초과가 88퍼쯤에서 시간초과가 났다.

 

시간 복잡도 계산을 해보니 최악의 경우 target * 모든 count의 합 이므로 100000 * 50000 > 십억을 초과해버린다.

 

다른 블로그를 보았더니 dp를 1차원이 아니라 2차원을 사용하고 있어서 이를 적용하였다.

 

이렇게하면 모든 count를 돌지않고 계산할 수 있다.

 

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

public class Main {
    public static int N, total;
    public static int[] value, count;
    public static int[][] dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for(int tc = 0; tc < 3; tc++){
            N = Integer.parseInt(br.readLine());
            total = 0;
            value = new int[N];
            count = new int[N];
            for(int i = 0; i < N; i++){
                st = new StringTokenizer(br.readLine());
                value[i] = Integer.parseInt(st.nextToken());
                count[i] = Integer.parseInt(st.nextToken());
                total += value[i] * count[i];
            }

            if(total % 2 == 1) System.out.println(0);
            else System.out.println(isValid());
        }
    }
    public static int isValid(){
        int target = total / 2;
        dp = new int[N + 1][target + 1];
        dp[0][0] = 1;

        for(int i = 1; i <= N; i++){
            int v = value[i - 1];
            int c = count[i - 1];

            for(int j = 0; j <= target; j++){
               if(dp[i - 1][j] == 1){
                   for(int k = 0; k <= v * c; k += v){
                       if(j + k <= target) dp[i][j + k] = 1;
                   }
               }
            }
        }

        if(dp[N][target] == 1) return 1;
        else return 0;
    }
}

 

오래걸렸지만 풀고 뿌듯했던 문제