b2629. 양팔저울

 

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

 

 

 

문제를 풀기 위해서는 dp[][] 의 규칙을 아는것이 가장 편하다.

이 문제의 규칙은 다음과 같다. 

 

1. dp[i][j] 는 boolean[N][M] 으로써 i 번째 추까지 사용했을 때 j무게를 확인할 수

있는가 없는가를 나타낸다. 또한 N은 추의갯수 M은 가능한 무게측정범위 즉 15001이 된다.

 

2. dp[i-1][j] 가 true라면 dp[i][j] 또한 true이다.

 

3. dp[i-1][ K ] 에서 true가 된다면

dp[i][K-i번째 추의 절댓값]과

dp[i][K+i번째 추의 절댓값]은 15001을 넘지않으면 true이다.

 

위의 규칙을 활용하여 나는 init method를 통해 초기화 및 입력을 받았으며

logic에서 N번째 추를 15000번 루프를 돌아 확인하고

true check를 통해서 풀이하였다.

 

 

 

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

public class Main {

    static int N,M;
    static int[] beads,weights;
    static boolean[][] dp;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        init(br);
        logic();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M ; i++) {
            if (beads[i] > 15000) sb.append("N ");
            else if(dp[N-1][beads[i]]) sb.append("Y ");
            else sb.append("N ");
        }
        System.out.println(sb);
    }

    private static void logic() {
        Arrays.sort(weights);
        dp[0][weights[0]]= true;
        for (int i = 1; i < N; i++) { //구슬 종류
            dp[i][weights[i]]= true;
            for(int j = 0 ; j < 15001; j++) { // 이전 무게 위치
                if(dp[i-1][j]) {
                    dp[i][j] = true;
                    int sum = Math.abs(j + weights[i]);
                    dp[i][Math.abs(j - weights[i])] = true;
                    if (sum <= 15000)
                        dp[i][sum] = true;
                }
            }
        }
    }

    private static void init(BufferedReader br) throws IOException {
        N = Integer.parseInt(br.readLine());
        weights = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            weights[i] = Integer.parseInt(st.nextToken());

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

        dp = new boolean[N][15001];
    }
}