[백준] 2629번 - 양팔저울 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 추들을 활용해 양팔저울에서 구슬의 무게를 측정할 수 있는지 여부를 구하는 문제다. 배낭 문제를 응용한 문제로 추들의 조합으로 특정 무게를 맞출 수 있는지 여부를 찾아야 한다. 구슬의 무게를 측정하는게 구슬 반대편에 추들을 배치하는 식으로 추들의 무게의 합으로 측정할 수도 있지만 구슬이 있는 쪽에 일부 추를 둬서 무게를 측정할 수 있다는 점에 주의해야 한다.

다이나믹 프로그래밍 과정에서 현재 추를 고려할 때 현재 추를 사용하지 않고 맞출 수 있는 무게는 측정 가능한 무게가 되고 현재 추를 사용할 때는 현재 추의 무게를 더한만큼의 무게도 측정 가능한 무게가 되며 현재 추의 무게를 뺀만큼의 무게도 측정 가능한 무게가 된다. 이때 뺀 결과가 음수가 나오면 구슬을 반대편에 두면 되므로 음수의 절댓값에 해당하는 무게가 측정 가능한 무게가 된다.

---

2. 코드

1. Bottom-Up 2차원 dp [Java]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] W = new int[1 + N];
        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            sum += W[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());

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

        boolean[][] dp = new boolean[1 + N][1 + sum];
        dp[0][0] = true;  // 추가 주어지지 않아도 구슬의 무게가 0이면 측정 가능
        for (int i = 1; i <= N; i++) {
            int w = W[i];

            for (int j = 0; j <= sum; j++) {
                if (!dp[i - 1][j]) continue;

                dp[i][j] = true;  // 현재 추를 사용하지 않는 경우
                dp[i][j + w] = true;  // 현재 추를 사용하는 경우
                dp[i][Math.abs(j - w)] = true;  // 현재 추를 사용하는 경우
            }
        }

        for (int bead : beads) {
            // 구슬의 무게가 모든 추의 무게보다 크거나 추의 조합으로 측정 불가능하면 N
            if (bead > sum || !dp[N][bead]) {
                sb.append("N ");
            } else {
                sb.append("Y ");
            }
        }

        System.out.println(sb);
    }
}

2. Bottom-Up 2차원 dp [C++]

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX = 100001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> wa(n);
    for (int& x : wa) cin >> x;

    int sum = 0;
    for (int x : wa) sum += x;

    int m;
    cin >> m;

    vector<int> ba(m);
    for (int& x : ba) cin >> x;

    vector<vector<bool>> dp(1 + n, vector<bool>(1 + sum));
    dp[0][0] = true;  // 추가 주어지지 않아도 구슬의 무게가 0이면 측정 가능
    for (int i = 1; i <= n; i++) {
        int w = wa[i - 1];

        for (int j = 0; j <= sum; j++) {
            if (!dp[i - 1][j]) continue;

            dp[i][j] = true;           // 현재 추를 사용하지 않는 경우
            dp[i][j + w] = true;       // 현재 추를 사용하는 경우
            dp[i][abs(j - w)] = true;  // 현재 추를 사용하는 경우
        }
    }

    for (int b : ba) {
        // 구슬의 무게가 모든 추의 무게보다 크거나 추의 조합으로 측정 불가능하면 N
        if (b > sum || !dp[n][b]) {
            cout << "N ";
        } else {
            cout << "Y ";
        }
    }
}

---

3. 풀이 정보

1. Bottom-Up 2차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	108 ms	14596 KB	1708 B

2. Bottom-Up 2차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2156 KB	1171 B

---