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

https://www.acmicpc.net/problem/2629

 

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

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

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

---

1.  아이디어

 

TopDown, BottomUp 다이나믹 프로그래밍을 활용해서 해결했다.

---

2. 문제풀이

 

TopDown 방식은 부분집합을 구하는 재귀 메서드와 메모이제이션을 활용했는데 부분집합은 해당 추를 사용하지 않거나 왼쪽 팔에 추를 올리거나 오른쪽 팔에 추를 올리는 3가지 경우가 있다.
추의 개수가 최대 30개이므로 모든 경우의 수는 3^30가지가 되고 이건 시간초과가 발생하게 된다. 이를 해결하기 위해 boolean 타입 2차원 배열을 활용해 해당 추까지 주어졌을 때 구할 수 있는 무게를 방문 체크하고 방문된 경우를 만나면 바로 종료하도록 했다.
파라미터로는 추의 번호와 구할 수 있는 무게를 들고 다녔고 구할 수 있는 무게는 왼쪽 팔 - 오른쪽 팔로 설정했다. 다만 이때 오른쪽 팔이 더 무거워서 음수가 나와도 무게를 잴 수 있으므로 절댓값을 씌워줬다.

BottomUp 방식은 일반적인 2차원 dp 테이블을 활용한 배낭 문제로 접근했고 각 추마다 역시 3가지 케이스가 존재한다. 현재 추를 사용하지 않는 경우에는 현재 추가 없던 조건에서 구할 수 있는 무게면 역시 구할 수 있고, 
현재 추를 사용하는 경우 왼쪽 팔에 사용하면 더하는 방향, 오른쪽 팔에 사용하면 빼는 방향이 된다.

---

3. 코드

 

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

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

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

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

        boolean[][] dp = new boolean[1 + N][1 + max];
        dp[0][0] = true;

        for (int i = 1; i <= N; i++) {
            dp[i][0] = true;

            for (int j = 1; j <= max; j++) {
                if (dp[i - 1][j]) dp[i][j] = true;
                if (j - weight[i] >= 0 && dp[i - 1][j - weight[i]]) dp[i][j] = true;
                if (dp[i - 1][j]) dp[i][Math.abs(j - weight[i])] = true;
            }
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            int ball = Integer.parseInt(st.nextToken());

            if (ball > max || !dp[N][ball]) sb.append("N ");
            else sb.append("Y ");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

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

public class Main_TopDown_DP {

    private static int N;
    private static int[] weight;
    private static boolean[][] dp;

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

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

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

        dp = new boolean[1 + N][1 + max];
        recur(0, 0);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            int ball = Integer.parseInt(st.nextToken());

            if (ball > max || !dp[N][ball]) sb.append("N ");
            else sb.append("Y ");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static void recur(int n, int w) {
        if (dp[n][w]) return;
        dp[n][w] = true;

        if (n == N) return;

        recur(n + 1, w);
        recur(n + 1, w + weight[n + 1]);
        recur(n + 1, Math.abs(w - weight[n + 1]));
    }

}

---

4. 후기

 

- BottomUp DP

- TopDown DP