[BOJ] 2629. 양팔저울

문제 원본 : https://www.acmicpc.net/problem/2629

2629번: 양팔저울

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] arr2 = new int[10000];
        int[] dp = new int[40001];
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            arr[i] = Integer.parseInt(st.nextToken());

            dp[arr[i]] = 1;
            arr2[cnt++] = arr[i];

            int tmp = cnt - 1;
            for (int j = 0; j < tmp; ++j) {
                if (dp[arr[i] + arr2[j]] == 0) {
                    dp[arr[i] + arr2[j]] = 1;
                    arr2[cnt++] = arr[i] + arr2[j];
                }
            }
        }

        Arrays.sort(arr2, 0, cnt);

        for (int i = 1; i < cnt; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[arr2[i] - arr2[j]] = 1;
            }
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < m; ++i) {
            if (dp[Integer.parseInt(st.nextToken())] == 1) {
                builder.append("Y ");
            } else {
                builder.append("N ");
            }
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }
}

• 다이내믹 프로그래밍 문제
• 첫 이중 for 문은 추를 한쪽에 한 개씩 전부 올리는 경우를 계산한다.
• 두 번째 이중 for 문은 한쪽에 두 개 이상 올려져 있을 때 반대쪽으로 옮기는 경우를 계산한다.