2629번. 양팔저울

 

아이디어

어떤 무게를 측정할 수 있는 상태에서 X g 짜리 구슬을 하나 추가한다면

'측정할 수 있는 무게 + X,    |측정할 수 있는 무게 - X|'

이 2가지 무게 또한 측정할 수 있게 된다.

 

dp[i][j] 를 i번째 구슬까지 추가했을 때 j 무게를 측정할 수 있는지 여부라고 정의한다면

 

dp[i][j] = dp[i - 1][j] 또는 dp[i - 1][ | j - j번째 구슬 무게 | ]  또는 dp[i - 1][j + j번째 구슬 무게]

 

가 된다.

 

측정할 수 있는 무게의 최대치는 모든 구슬 무게의 합이므로 이 값을 j 의 최대 범위로 설정해서 dp 배열을 만들면 된다.

 

풀이코드

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

public class _n2629_ {
    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];
        int V = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            weights[i] = Integer.parseInt(st.nextToken());
            V += weights[i];
        }

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

        for (int i = 1; i <= N; i++) {
            int weight = weights[i];

            for (int j = 0; j <= V; j++) {
                if (j + weight <= V) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][Math.abs(j - weight)] || dp[i - 1][j + weight];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][Math.abs(j - weight)];
                }
            }
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(st.nextToken());

            if (target <= V && dp[N][target]) {
                result.append("Y");
            } else {
                result.append("N");
            }
            result.append(" ");
        }

        System.out.println(result);
    }
}