[백준] Q17610 양팔저울 JAVA

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

17610번: 양팔저울

 

1. 문제의 유형 및 이해

완전탐색

서로다른 K개의 추를 양팔저울을 한번만 비교하여 원하는 무게를 그릇에 담고자 한다.

{1,2,6}의 추가 주어질 때 , 만들 수 있는 모든 경우의 수는 다음과 같다. (ㅁ : 그릇)

그릇에 4만큼의 무게를 담고자 할때는 가지고 있는 추 2, 6을 이용하여

(ㅁ + 2) = 6 을 통해 ㅁ = 4 를 만들어 낼 수 있다.

모든 추의 합이 S라고 할 때 1~ S 중 만들지 못하는 경우의 수를 찾아보자.

 

처음 문제를 볼 때,  '부분 합' 이 먼저 떠올랐습니다.

K= 13으로 모든 부분합 개수는 $2^{13}$ = 8192 가지로 충분히 구할 수 있습니다.

 

처음 푼 풀이와 풀고 나서 알게 된 풀이를 포스팅하고자 합니다.

2. 문제 접근 방법

처음 접근 방법

구하고자 하는 값을 생각해보면 [그릇 + X 부분합] : [S-X의 부분합] 으로 모든 그릇의 개수를 구할 수 있다고 생각했습니다.

집합의 경우 bit연산을 통해 충분히 계산가능한 크기라고 생각했습니다.

0110 이라고 한다면 1을 포함하지 않는 부분합의 크기들에 대해 모두 구하여 그릇의 크기를 구하였습니다.

[0110] + 그릇 = [1001] [1000] [0001] [0000] 이라고 할 때

그릇이 담을 수 있는 크기는 S-X의 부분합 - X의 부분합 으로 접근하였습니다.

이 때 그릇이 담을 수 있는 크기는 중복이 될 수 있으므로 set연산을 통해 중복을 제거하였습니다.

부분합을 담을 배열 arr을 arr[ 1<<N]만큼 정해두고 부분합마다의 값을 기록해두고 계산 하였습니다.

package DayByDay._0324;

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

/**
 * @문제번호 : Q17610
* @문제이름 : 양팔저울
 * @난이도 : Silver I
 * @date : 2022-03-24 오후 2:49
 * @author : pcrmcw0486
 * @문제이해
 * 무게가 서로 다른 k개의 추와 빈 그릇이 있다.
 * 모든 추의 무게는 정수이고 그릇의 무게는 0이다.
 * 양팔 저울을 한번만 이용하여 원하는 무게의 물을 그릇에 담으려고 한다.
 * @알고리즘
 * 완전탐색
 * @접근방법
 * 양팔저울 한번을 통해 잴 수 있는 무게는
 * 어떤 추들의 합 x에 대해 X와 S-X를 만들어 낼 수 있다.
 * 어떤 추들의 합X는 추 집합 K의 부분 집합들이다.
 * K가 13개가 주어질 때, 1~S중 양팔 저울을 한번만 이용하여 측정이 불가능한 경우의 수를 찾아보자.
 * 불가능한 경우의 수 구하기.
 * 정해진 정답의 범위는 1~S
 * k가 13일 때 나올 수 있는 부분집합 개수는 2^13 = 8192개이다.
 * 근데 과연 다 구하는게 좋을까? 최적화할 수 있는 방법은 없을 까?
 * 절반만 뽑으면 모든 경우의수를 보는 것과 같다. X  S-X이기 때문에.
 * 그리고 같을 수도 있다.S의 최대크기는 2,600,000
 *
 * 조금 더 쉽게 생각하면 왼쪽에 올린다 오른쪽에 올린다 안올린다 3가지 상태...
*/
public class Main {
    static int N, S, cnt, TOT;
    static int[] data;
    static int[] arr;
    static boolean[] pos;
    static Set<Integer> set;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine()); S=0;
        data = new int[N];
        TOT =1<<N;
        arr = new int[TOT];
        set = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            data[i] = Integer.parseInt(st.nextToken());
            S += data[i];
        }
        arr[TOT-1] = S;
        pos = new boolean[S+1];
        solve(0,0,0);
        for (int i = 1; i < TOT; i++) {
            for (int j = 0;j < TOT; j++) {
                if((i & j) == 0){
                    set.add(Math.abs(arr[i] - arr[j]));
                }
            }
        }
        set.remove(0);
        System.out.println(S-set.size());
    }

    private static void solve(int depth, int value, int status) {
        if( depth == N){
            arr[status] = value;
            arr[status^(TOT-1)] = S-value;
            return;
        }
        solve(depth+1,value,status);
        solve(depth+1,value+ data[depth],(status | (1<<depth)));
    }

    private static void dfs(int depth, int weight){
        if(depth == N){
            if(weight > 0){
                pos[weight]= true;
            }
            return;
        }
        dfs(depth+1, weight);
        dfs(depth + 1, weight + data[depth]);
        dfs(depth + 1, weight - data[depth]);
    }
}

 

이 방법의 경우 [2+ㅁ] = 6 과 [6+ㅁ] = 2와 같이 중복되는 연산이 매우 많이 들어가게 됩니다.

N이 6일 때만 해도

[{1,2,3} + ㅁ]  = ${N}_C_{6-3}$ 의 횟수 만큼 반복되는 걸 또 두번씩 하게 되기 때문에 시간이 오래 걸립니다.

 

이후의 풀이

처음에 접근했던 것을 다시 생각해보면 [X 부분합] + ㅁ = [S-X의 부분합]을 구하고 싶었습니다.

이때 ㅁ의 크기는 {S-X}부분합 - {X}의 부분합 으로 정할 수 있구요.

S-X를 오른쪽 저울, X를 왼쪽 저울이라고 생각하면

그렇다면 우리는 배열을 돌면서 왼쪽 저울에 올릴지, 오른쪽 저울에 올릴지만 정하면 됩니다.

이 때 한번 더 생각해야할 것은, 저울에 올리지 않는 경우까지도 생각해주면됩니다.

즉, 구하고자 하는 weight값은 

weight + 추(오른쪽 저울에 올린다)

weight - 추 (왼쪽 저울에 올린다) 

weight( 안 올린다)

의 모든 경우의 수를 구해주게 되면 됩니다.

위 코드의 dfs함수를 참조하시면 됩니다.

 

집합을 나누어 각 집합에 넣어주는 행위에 대해 잘 생각해보면 좋을것 같습니다.