BOJ 2629 양팔저울

문제

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

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

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

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

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

입력

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

출력

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

문제 분석

문제 분석
1. 정보
- 추의 무게와, 확인할 구슬들의 무게가 주어짐
- 추와 구슬을 적절히 배치하여 균형을 이루면 구슬의 무게를 알 수 있음
- 해당 문제에서는 추의 무게와, 구슬의 무게가 주어짐

2. 목표

   • 주어진 추를 사용하여, 구슬의 무게를 확인할 수 있으면 Y, 아니면 N을 출력

3. 제약 조건

   • 추의 개수 $\le 30$
   • 추의 무게 $\le 500$
   • 구슬의 개수 $\le 7$
   • 구슬의 무게 $\le 40000$

풀이

1. 알고리즘

   • DP 알고리즘
     • dp[i][j] : 구슬을 i번째까지 사용했을 때, 무게 j 가능 유무 판별
       • dp[0][0] = true
       • i : 0 ~ N까지
       • j : 0 ~ 구슬의 최대 합까지
       • dp[i]j + weight[i]] : 추를 구슬 반대편에 올릴 경우
       • dp[i]j - weight[i]] : 추를 구슬 같은편에 올릴 경우
       • dp[i][j] : 추를 사용하지 않을 경우

코드

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

public class BOJ2629 {

    private static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] weight = new int[N];
        int weightSum = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            weight[i] = Integer.parseInt(st.nextToken());
            weightSum += weight[i];
        }

        boolean[][] dp = new boolean[N + 1][weightSum * 2 + 1];
        dp[0][weightSum] = true;

        for (int i = 1; i <= N; i++) {
            for (int j = -weightSum; j <= weightSum; j++) {
                if (dp[i - 1][j + weightSum]) {
                    dp[i][j + weightSum] = true; //추 사용 X
                    if(j + weightSum + weight[i - 1] <= weightSum * 2) dp[i][j + weightSum + weight[i - 1]] = true; //추를 구슬 반대편에

                    if(j + weightSum - weight[i - 1] >= 0) dp[i][j + weightSum - weight[i - 1]] = true; //추를 구슬 같은편에
                }
            }
        }

        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int cur = Integer.parseInt(st.nextToken());
            if (cur > weightSum) {
                sb.append("N ");
            }else{
                sb.append(dp[N][cur + weightSum] ? "Y" : "N").append(" ");
            }
        }
        System.out.println(sb.toString());
    }

    public static void main(String[] args) throws IOException {
        BOJ2629.solution();
    }
}