백준 2629번 - 양팔저울

문제

백준 2629번 - 양팔저울

아이디어

• 확인하고자 하는 구슬들의 입력을 받을 때마다 계산하지 않고 dp 테이블로 미리 결과를 구해놓고 dp 테이블을 참조해 결과를 출력한다.
• dp[i][j]를 i번째 추까지 저울에 올렸을 때 j 무게를 알 수 있는지 여부라고 가정한다.
• 구슬을 항상 왼쪽에 놓는다고 봤을 때 추를 왼쪽에 올리면 구슬 + 추 무게를 알 수 있고, 추를 오른쪽에 올리면 구슬 - 추의 무게를 알 수 있다. 당연히 추를 올리지 않을 때도 알 수 있다.

예상 시간 복잡도

• 추의 개수 : N
• 추의 최대 무게 : M
• 예상 시간 복잡도 : O(N x M)

코드 구현

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

public class BJ_2629 {

    static final int MAX_WEIGHT = 15000;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] weights = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            weights[i] = Integer.parseInt(st.nextToken());
        }

        boolean[][] dp = new boolean[n + 1][MAX_WEIGHT + 1];
        dp[0][0] = true;

        for (int i = 1; i <= n; i++) {

            int weight = weights[i];

            for (int j = 0; j <= MAX_WEIGHT; j++) {

                if (dp[i - 1][j]) { //이전 번째에서 해당 무게를 만들 수 있을 때만

                    dp[i][j] = true; //추를 올리지 않는 경우

                    if (weight + j <= MAX_WEIGHT) { //추를 왼쪽에 올리는 경우
                        dp[i][weight + j] = true;
                    }

                    if (Math.abs(j - weight) <= MAX_WEIGHT) { //추를 오른쪽에 올리는 경우
                        dp[i][Math.abs(j - weight)] = true;
                    }
                }
            }
        }

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

        st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());

            if (num <= MAX_WEIGHT && dp[n][num]) {
                sb.append("Y ");
            } else {
                sb.append("N ");
            }
        }
        System.out.print(sb);
    }
}