BOJ_2629_양팔 저울 (Java)

[Gold III] 양팔저울 - 2629

문제 링크

성능 요약

메모리: 15584 KB, 시간: 112 ms

분류

다이나믹 프로그래밍, 배낭 문제

제출 일자

2025년 1월 2일 17:15:20

문제 설명

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

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

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

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

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

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

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

입력

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

출력

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

문제 풀이

dp배열에 dp[i][j]의 값은 i번째까지 골랐을 때 j란 값을 만들 수 있는지 없는지를 뜻한다. 고로 j란 값을 만들 수 있는지를 체크하기 위해선 1~N 개를 골랐을 때 num라는 값을 만들 수 있는지를 체크해야 하는 것이다. 따라서 dp[1][num] ~ dp[N][num]가지 검사해서 true가 있으면 만들 수 있다는 것!

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M, weight[], arr[];
    static boolean[][] dp;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2629_양팔저울/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        weight = new int[N];
        dp = new boolean[31][500 * 30 + 1]; // 추 30개 , 각 500g이하 -> 무게 1~15000
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            weight[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0);

        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());
            if (arr[i] > 15000) sb.append("N").append(" ");
            else {
                boolean flag = false;
                for (int j = 0; j <= N; j++) {
                    if (dp[j][arr[i]]) {
                        flag = true;
                        break;
                    }
                }
                sb.append(dp[N][arr[i]] ? "Y" : "N").append(" ");
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private void dfs(int idx, int sum) {

        if (idx > N || sum > 15000 || dp[idx][sum]) return;

        dp[idx][sum] = true;

        if (idx == N) return;

        dfs(idx + 1, Math.abs(sum - weight[idx]));
        dfs(idx + 1, sum);
        if (sum + weight[idx] <= 15000) dfs(idx + 1, sum + weight[idx]);

    }
}