[백준/Java] 2629 : 양팔저울

백준 2629번 '양팔저울' 풀이입니다. 추들로 만들 수 있는 모든 무게 차이를 DP로 구한 뒤, 구슬의 무게가 해당 차이와 같은지 확인하는 방식입니다. 상태를 구슬 무게가 아닌 양쪽 무게 차이로 정의하는 것이 핵심으로, 0/1 배낭 문제의 변형입니다. 각 추를 사용할 때 같은 편(+w)과 반대편(|d-w|)에 추가하는 두 가지 전이가 발생합니다.

---

📌 문제 정보

• 번호: 2629
• 제목: 양팔저울
• 난이도: Gold 3
• 분류: 다이나믹 프로그래밍, 배낭 문제

---

💡 접근 방식

추들을 이용해 만들 수 있는 모든 차이를 구한 뒤, 구슬의 무게가 해당 차이와 같은지 확인하여 해결했습니다.

• dp[d]를 사용하여 무게 차이가 d가 될 수 있는지 여부를 저장
• 같은 추를 여러 번 사용하는 것을 방지하기 위해 temp 배열로 한 단계씩 갱신

---

💻 핵심 코드

dp[0] = true;

for (int w : weight) {
    boolean[] temp = new boolean[40001];

    for (int d = 0; d <= 40000; d++) {
        if (!dp[d]) continue;

        if (d + w <= 40000) temp[d + w] = true;
        temp[Math.abs(d - w)] = true;
    }

    for (int d = 0; d <= 40000; d++) {
        if (temp[d]) dp[d] = true;
    }
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(N × 40000)
• 공간 복잡도: O(40000)

---

📄 전체 코드

package B2629;

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

public class Main {
    static int N, M;
    static int[] weight;
    static int[] bead;
    static boolean[] dp = new boolean[40001];

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

        N = Integer.parseInt(br.readLine().trim());
        weight = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) weight[i] = Integer.parseInt(st.nextToken());

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

        dp[0] = true;
        for (int w : weight) {
            boolean[] temp = new boolean[40001];
            for (int d = 0; d <= 40000; d++) {
                if (!dp[d]) continue;
                temp[d + w] = true;
                temp[Math.abs(d - w)] = true;
            }
            for (int d = 0; d <= 40000; d++) if (temp[d]) dp[d] = true;
        }

        for (int i = 0; i < M; i++) {
            sb.append(dp[bead[i]] ? "Y" : "N").append(" ");
        }
        System.out.println(sb);
    }
}