[백준] 양팔저울_17610

문제

무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고 그 무게가 각각 {1, 2, 6}이면, S = 9이고, 양팔 저울을 한번만 이용하여 1부터 S사이 모든 정수에 대응하는 물을 다음과 같이 그릇에 담을 수 있다. 여기서, X는 그릇에 담는 물의 무게를 나타내고, □는 그릇을 나타낸다.

  X        1           2                 3                      4                     5                6                7                       8                        9

□:1

□:2

□:(1+2)

(□+2):6

(□+1):6

□:6

□:(1+6)

□:(2+6)

□:(1+2+6)

만약 추의 무게가 {1, 5, 7}이면 S = 13이 되고, 양팔저울을 한 번만 사용하여 그릇에 담을 수 있는 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이다. 즉, 1부터 S사이 수 가운데 9와 10에 대응하는 무게의 물을 그릇에 담는 것은 불가능하다.

k(3 ≤ k ≤ 13)개 추 무게 g1, g2, ..., gk가 주어질 때, 1부터 S사이에 있는 정수 중, 양팔 저울을 한번만 이용하여서는 측정이 불가능한 경우의 수를 찾는 프로그램을 작성하고자 한다.

입력

입력의 첫 줄에는 추의 개수를 나타내는 정수 k(3 ≤ k ≤ 13)가 주어진다. 다음 줄에는 k개의 정수 gi(1 ≤ gi ≤ 200,000)가 공백으로 구분되어 주어지는데 이는 각 추의 무게를 나타낸다.

출력

1부터 S(추 무게의 합) 사이에 있는 정수 중, 양팔 저울을 한번만 이용해서는 측정이 불가능한 경우의 수를 출력한다.

예제 입력 1

3
1 5 7

예제 출력 1

2

 

추를 저울에 놓는 방법에는 세가지가 있다. 0 : 넣지 않는다, 1: 왼쪽에 넣는다, 2: 오른쪽에 넣는다.

이를 바탕으로 추를 넣을 수 있는 모든 방법을 찾은 후

왼쪽에 추가 올라갔다면 -를, 오른쪽에 추가 올라갔다면 +하여 계산하면 측정할 수 있는 무게를 찾을 수 있다.

1부터 추들의 합까지 넣을 수 있는 배열을 만들어

구할 수 있다면 1을, 구할 수 없다면 0 을 넣은 후 

0의 갯수를 세어서 구할 수 없는 숫자의 갯수를 파악할 수 있다.

 

풀이 코드

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

public class 양팔저울_17610 {

    static int n;
    static int sum;
    static int[] answer;
    static int[] ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);

        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] weight = new int[n];
        answer = new int[n];
        int[] LR = {0,1,2};
        sum = 0;

        for(int i = 0; i<n; i++){
            weight[i] = Integer.parseInt(st.nextToken());
            sum += weight[i];
        }

        ans = new int[sum];
        int cnt = 0;
        canMake(0,LR, weight);

        for(int i = 0; i<ans.length; i++){
            if(ans[i] == 0) {
                cnt++;
            }
        }

        pw.println(cnt);

        br.close();
        pw.close();

    }

    public static void canMake(int cnt, int[] LR, int[] weight) {
        if(cnt == n) {
            int result = 0;
            for(int i = 0; i<answer.length; i++){
                if(answer[i] == 1) {
                    result -= weight[i];
                } else if(answer[i] == 2) {
                    result += weight[i];
                }

                if(result > 0 && result <=sum) {
                    ans[result-1] = 1;
                }
            }
            return;
        }

        for(int i = 0; i<LR.length; i++){
            answer[cnt] = LR[i];
            canMake(cnt+1,LR, weight);
        }

    }
}