[Java] 백준 1943 동전 분배

오늘의 문제 : https://www.acmicpc.net/problem/1943

 

그리디로 풀다가 실패해서 백트래킹으로 다시 도전 후 또 실패하고 정답을 맞힌 문제입니다.

 

1. 그리디

 

동전을 내림차순으로 정렬 후 현재 더 적은 금액을 가지고 있는 사람에게 동전을 주도록 하였습니다.

 

그럴 듯 하지만...

3
13 1
3 1
2 8

위와 같은  상황에서는 적절하지 못하게 동전을 분배합니다. (제가 직접 생각했어요 뿌듯)

 

2. 백트래킹

 

모든 경우를 전부 확인해야 한다고 생각하여, 백트래킹을 통해 확인했습니다. 

 

하지만 테스트 케이스 3개 * 2의 n*n(대략)의 시간복잡도가 나오기 떄문에 시간을 초과하게 됩니다. 

 

- 백트래킹 코드

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

public class Main {
    static int sum1,sum2;
    static boolean answer;
    private static class Pair{
        int value;
        int cnt;
        Pair(int value,int cnt){
            this.value = value;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<3;i++){
            int n = Integer.parseInt(br.readLine());
            int totalSum = 0;
            List<Integer> list = new ArrayList<>();
            for(int j=0;j<n;j++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                int value = Integer.parseInt(st.nextToken());
                int cnt = Integer.parseInt(st.nextToken());
                totalSum += (value*cnt);
                while(cnt>0){
                    cnt--;
                    list.add(value);
                }

            }
            sum1 = 0;
            sum2 = 0;
            answer = false;
            find(list,totalSum,0);
            if(answer){
                sb.append(1).append("\n");
            }else{
                sb.append(0).append("\n");
            }
        }
        System.out.print(sb);
    }
    public static void find(List<Integer> list, int totalSum,int i){
        if(answer) return;
        if(i == list.size()){
            if(sum1 == sum2) answer = true;
            return;
        }
//        System.out.println(sum1+" "+sum2);
        int value = list.get(i);
        if(sum1 == sum2){
            sum1 += list.get(i);
            totalSum -= list.get(i);
            find(list,totalSum,i+1);
        }else if(sum1 > sum2){
            totalSum -= value;
            if(sum1 + value <= totalSum){
                sum1 += value;
                find(list,totalSum,i+1);
                sum1 -= value;
            }
            sum2 += value;
            find(list,totalSum,i+1);
            sum2 -= value;
        }else{
            totalSum -= value;
            if(sum2 +value <= totalSum){
                sum2 += value;
                find(list,totalSum,i+1);
                sum2 -= value;
            }
            sum1 += value;
            find(list,totalSum,i+1);
            sum1 -= value;
        }
    }
}

 

 

3. DP

 

백트래킹에서 시간 복잡도를 줄이기 위해 DP를 도입하기로 했습니다. 

 

신기하게도 백트래킹을 한번 구현하고나니 점화식을 좀 더 쉽게 생각할 수 있는 줄 알았는데, 아니더라고요. 

 

우선 위 백트래킹 코드에서 필요없는 변수들을 지워줬습니다.

 

- sum2 변수는 값은 남아있는 totalScore의 값과 동일한 의미

 

그리고 위 코드가 중복이 발생하는 부분을 생각해 보았습니다. 

 

만일 sum1 = 700 인700인 경우 동전을 나누기 함수가 진행되고, sum1 = 300 + 400 = 700인 경우에도 함수가 진행되게 됩니다. 하지만 둘 중 하나의 경우가 동전 나누기가 실패했다면, 다른 하나도 당연히 실패하게 됩니다. 

 

헉 

 

즉 sum1에 대해서 같은 값을 가지는 함수에 대해서는 실행하지 않아도 됩니다.  

 

이를 위해  100,000원을 넘지 않는다." 라는 조건을 통해 dp [] = new boolean[100_001]   만들어 코드를 작성했습니다. 

 

코드

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

public class Num1943동전_분배 {
    static int sum1,sum2;
    static boolean answer;
    private static class Pair{
        int value;
        int cnt;
        Pair(int value,int cnt){
            this.value = value;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<3;i++){
            int n = Integer.parseInt(br.readLine());
            int totalSum = 0;
            List<Integer> list = new ArrayList<>();
            for(int j=0;j<n;j++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                int value = Integer.parseInt(st.nextToken());
                int cnt = Integer.parseInt(st.nextToken());
                totalSum += (value*cnt);
                while(cnt>0){
                    cnt--;
                    list.add(value);
                }

            }
            sum1 = 0;
            answer = false;
            boolean[] dp = new boolean[100_001];
            find(list,dp,totalSum,0);
            if(answer){
                sb.append(1).append("\n");
            }else{
                sb.append(0).append("\n");
            }
        }
        System.out.print(sb);
    }
    public static void find(List<Integer> list,boolean[] dp,int totalSum,int i){
        if(answer) return;
        if(sum1 == totalSum){
            answer = true;
            return;
        }
        if(i == list.size()){
            dp[sum1] = true;
            return;
        }
        int value = list.get(i);
        if(sum1 < totalSum){
            if(sum1 + value <= totalSum && !dp[sum1+value]){
                dp[sum1+value] = true;
                totalSum -= value;
                sum1 += value;  
                find(list,dp,totalSum,i+1);
                sum1 -= value;
                totalSum += value;
            }
            find(list,dp,totalSum,i+1);
        }
    }
}

 

후기 

탐색의 종료 조건이 살짝 맘에 안드는데, 혹시 더 깔끔한 방법 있으면 알려주세요. 

알려주신 분은..음..제 블로그 VIP 자격 드립니다.