2629 - 양팔저울[G3]

 

문제

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

 

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

입력

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

출력

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.

 

 

풀이

 

풀이의 핵심은 저울을 놓았을 때, 모든 경우의 수를 구하는 것.

처음에는 이를 백트래킹으로 구현하였으나, 당연히도 시간 초과(겸 메모리 초과)로 실패하였다.

 

중점은 DP 배열을 사용하는 것이다,

처음에는 2차원 배열을 고민하였다. (boolean [왼쪽 저울][오른쪽 저울] = true/false)를 통해 값을 비교해 볼 수 있다고 생각했다.)

 

하지만 이보다는 그냥 모든 값이 나올 수 있는 1차원 배열의 경우를 고민하였다.

이 경우 추의 값을 가장 높은 값부터 순회한다.

 

1. 0번째 값은 0이며, 항상 true(가능)하다.

2. 저울의 배열을 순환하며, 현재 저울 값을 가진 dp[value]를 true 처리한다. (단, Queue를 두어 모든 연산이 끝난 뒤 추가하게 한다.)

[즉, 모든 경우의 수를 for 루프를 통해 순회한다. 코드를 참조하자. ]

3. 만약 '현재 저울 값'이 아닌 값에 true가 되어 있다면, 다음의 경우를 고려할 수 있다.

3-1 : 이 저울에 값을 추가하기 -> true + 현재 저울 값이 유효하다면, 이 값 역시 Queue에 추가한다(나중에 true 처리)

3-2 : 반대로 저울의 '왼쪽' 에도 값을 할당할 수 있다. -> true - 현재 저울 값이 유효하다면, 이 값을 Queue에 추가한다.

4. 최종적으로 모든 경우의 수를 dp 배열에 할당할 수 있다.

코드

 

import java.util.*; 
import java.io.*;
class Main {
    static int W, T, sumOfWeight;
    static int[] weights;
    static boolean[] isUsed; //backtracking 체크용
    static int[] marbles;
    static boolean[] dp; //경우의 수
    static Queue<Boolean> answer = new ArrayDeque<>();
    public static void main(String[] args) throws Exception {
        input();
        setting();
        for (int i = 0; i < T; i++) solve(i);
        output();
    }

    static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while (!answer.isEmpty()) {
            if (answer.poll()) bw.write("Y ");
            else bw.write("N ");
        }
//        System.out.println(Arrays.toString(dp));
        bw.close();
    }

    static void solve(int idx) {
        int marble = marbles[idx];
        if(marble <= sumOfWeight && dp[marble]) answer.add(true);
        else answer.add(false);
    }

    //경우의 수 DP를 통해 구하기
    static void setting() {
//        // dp 배열 초기화
//        dp = new boolean[sumOfWeight+1][sumOfWeight + 1];
//        dp[0][0] = true; // 아무 추도 사용하지 않았을 때 0은 항상 만들 수 있음
//
//        // 모든 추에 대해 반복
//        for (int i = 1; i <= W; i++) {
//            int weight = weights[i-1]; // i번째 추의 무게
//            for (int j = 0; j <= sumOfWeight; j++) {
//                dp[weight][weight] = true; //현재 무게
//                if (dp[i-1][j]) { // 이전 추까지 고려한 결과가 true인 경우
//                    dp[i][j] = true; // 현재 추를 사용하지 않는 경우 (이전 추의 값 그대로 받아옴)
//                    if (j + weight <= sumOfWeight) dp[i][j + weight] = true; // 현재 추를 더하는 경우
//                    if(j >= weight) { //구슬 위치(왼쪽)에 추를 더하는 경우
//                        dp[i][j - weight] = true;
//                    }
//                }
//            }
//        }

        dp = new boolean[sumOfWeight + 1];
        dp[0] = true;
        // 각 추에 대해 반복
        Queue<Integer> tempQueue = new ArrayDeque<>();
        for (int i = W - 1; i >= 0; i--) {
            int weight = weights[i];
            for (int j = dp.length - 1; j >= 0; j--) { //큰 수부터 하향식으로 진행 (아래 반복문에 중첩 발생 방지)
                if(dp[j]) { //이전값 고려, 추를 더하거나 빼거나
                    int newWeightPlus = j + weight;
                    int newWeightMinus = Math.abs(j - weight); //양팔 저울은 음수 값도 고려할 수 있어야 함.

                    //범위 안에서의 더하기, 중복 고려
                    if (newWeightPlus <= sumOfWeight && !dp[newWeightPlus]) {
                        tempQueue.add(newWeightPlus);
                    }
                    //반대로 추 빼기
                    if (newWeightMinus >= 0 && !dp[newWeightMinus]) {
                        tempQueue.add(newWeightMinus);
                    }
                }
            }
            while (!tempQueue.isEmpty()) {
                dp[tempQueue.poll()] = true; //적용
            }
        }
    }

    //시간 초과 발생..
//    static void backTracking(int nowWeight, int idx, boolean use) {
//        if(idx == weights.length) return;
//        isUsed[idx] = true;
//        if(use) nowWeight += weights[idx];
//        dp[nowWeight] = true;
//
//        backTracking(nowWeight, idx + 1, true);
//        backTracking(nowWeight, idx + 1, false);
//        isUsed[idx] = false;
//    }


    //입력받기
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        W = Integer.parseInt(br.readLine()); //저울추 개수
        weights = new int[W]; //추의 무게
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < W; i++) {
            weights[i] = Integer.parseInt(st.nextToken());
            sumOfWeight += weights[i];
        }
        T = Integer.parseInt(br.readLine()); //테스트 개수
        marbles = new int[T]; //구슬들의 무게
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < T; i++) {
            marbles[i] = Integer.parseInt(st.nextToken());
        }
    }
}