백준 2629[자바] java 양팔저울

문제 링크: https://www.acmicpc.net/problem/2629

2629번: 양팔저울

▶문제

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

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

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

<그림 1> 구슬이 3g인지 확인하는 방법 (1은 1g인 추, 4는 4g인 추, ●은 무게를 확인할 구슬)

<그림 2>와 같은 방법을 사용하면 구슬이 5g 인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인할 수 있는지를 결정하는 프로그램을 작성하시오.

<그림 2> 구슬이 5g인지 확인하는 방법

---

▶입력

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

---

▶출력

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

---

▶해설

DP + 재귀 아니면 DP + DFS로 풀 수 있는 문제였습니다. 저는 DP + DFS로 풀었습니다. 

 

추의 무게를 조합할 수 있는 방법을 살펴보겠습니다.

i. 이전까지의 추 무게 그대로

ii. 이전까지의 추 무게 + 현재 추의 무게

iii. 구슬쪽에 추를 추가했을 때 

 

i번과 ii번은 쉽게 구할 수 있었습니다. 하지만 iii번의 경우 음수가 있을 수 있어서 배열의 길이를 2배로 선언해서 구하려고 했지만, 복잡해져서 절댓값을 사용하기로 했습니다.

 

문제가 되는 iii번의 경우의 수를 보겠습니다. 

 

1. 이전까지의 추 무게 - 현재 추의 무게 >0

2. 이전까지의 추 무게 - 현재 추의 무게 <0

 

1번 경우: 구슬쪽에 추가해도 음수가 되지 않으므로 그냥 빼면 됩니다. 따라서 추를 계속 추가하는 곳은 변하지 않습니다.

 

2번 경우: 구슬쪽에 추가했을 때 음수가 됩니다. 그래서 구슬 쪽으로 기울게 됩니다. 이제 ii번에서 추를 추가하는 곳은 이전에 추를 추가한 곳이 아닌 구슬 쪽으로 변경하게 됩니다. 이렇게 음수가 될 때마다 추를 추가하는 곳이 변경됩니다. 따라서 음수가 나올 때마다 추를 추가하는 곳이 변경된다고 생각하시면 됩니다. 

 

전체 코드

import java.io.*;
import java.util.*;


public class Main {
    static int n, m;
    static int[] arr, map;
    static boolean[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new boolean[n + 2][40001];
        map = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            map[i] = Integer.parseInt(st.nextToken());
        }

        m = Integer.parseInt(br.readLine());
        arr = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dfs(1, 0);


        for (int j = 0; j < m; j++) {
            if (dp[n+1][arr[j]]){
                System.out.print("Y ");
            }
            else{
                System.out.print("N ");
            }
        }
    }

    private static void dfs(int count, int index) {
        if (dp[count][index]) {
            return;
        }
        dp[count][index] = true;

        if (count == n+1) {
            return;
        }

        dfs(count + 1, index + map[count-1]);
        dfs(count + 1, index);
        dfs(count + 1, Math.abs(index - map[count-1]));
    }
}