[BaekJoon] 2629 양팔저울 (Java)

1.  문제 링크

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

2.  문제

요약

• 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지 판별하는 문제입니다.
• 입력: 첫 번째 줄에 30보다 작거나 같은 자연수인 추의 개수가 주어지고 두 번째 줄에 500보다 작거나 같은 자연수인 추의 무게들이 가벼운 것부터 차례로 주어집니다. 세 번째 줄에는 7보다 작거나 같은 무게를 확인하고자 하는 구슬들의 개수가 주어지고 네 번째 줄에는 40,000보다 작거나 같은 자연수인 확인하고자 하는 구슬들의 무게가 주어집니다.
  • 추의 무게는 같은 무게가 여러 개 있을 수 있습니다.
• 출력: 첫 번째 줄에 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N을 빈칸을 하나씩 두어 출력합니다.

3.  소스코드

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

public class Main {
    static final int MAX = 15000;
    static StringBuilder sb = new StringBuilder();
    static int weightNum, checkNum;
    static int[] weights, checkedWeights;
    static boolean[][] visited;
    static void input() {
        Reader scanner = new Reader();
        weightNum = scanner.nextInt();
        weights = new int[weightNum];
        for(int idx = 0; idx < weightNum; idx++) weights[idx] = scanner.nextInt();
        checkNum = scanner.nextInt();
        checkedWeights = new int[checkNum];
        for(int idx = 0; idx < checkNum; idx++) checkedWeights[idx] = scanner.nextInt();
    }

    static void solution() {
        visited = new boolean[weightNum + 1][MAX + 1];
        dfs(0, 0);
        for(int idx = 0; idx < checkNum; idx++) {
            if(checkedWeights[idx] > MAX) sb.append('N').append(' ');
            else if(!visited[weightNum][checkedWeights[idx]]) sb.append('N').append(' ');
            else sb.append('Y').append(' ');
        }
        System.out.println(sb);
    }

    static void dfs(int index, int sum) {
        if(visited[index][sum]) return;
        visited[index][sum] = true;
        if(index == weightNum) return;
        dfs(index + 1, sum + weights[index]);
        dfs(index + 1, sum);
        dfs(index + 1, Math.abs(sum - weights[index]));
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• DFS 알고리즘을 통해 가지고 있는 추를 이용하여 확인할 수 있는 무게들을 구합니다.
  • 탐색 시에 세 가지 경우를 생각해볼 수 있습니다.
    1. 다음 추를 올려놓았을 때
    2. 다음 추를 올려놓지 않았을 때
    3. 다음 추를 반대쪽에 올렸을 때
  • 위 세 가지 경우에 대해 DFS 탐색을 진행하고 visited 배열을 이용해 각 탐색에서 어떠한 추에 어떤 무게들을 확인할 수 있는지 저장합니다.
• visited 배열을 통해 확인하고자 하는 구슬들의 무게들을 확인하고 방문했다면 Y를, 방문하지 않았다면 N을 출력합니다.