[JAVA] 백준 2629 - 양팔 저울

 

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

 

 

추를 (저울에 올리지 않는경우) , (오른쪽에 올리는 경우), (왼쪽에 올리는 경우)

총 세개로 재귀함수를 돌리면되는데, 그렇게 하면 문제의 조건에의해 시간 초과가 나므로, 

메모이제이션을통해 가지치기를 해야한다

 

 

dp[i][w] = i번째 추까지 있을때, 그것으로 만들수있는 무게 w

 

dp[i][w]의 의미를 제대로 규정짓지못해서 풀기 어려웠던 문제였다..

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {

    static int N;
    static int[] weight;
    static boolean[][] dp;
    static boolean[] ans;
    static int K;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        weight = new int[N + 1];
        ans = new boolean[15001];
        String[] lines = br.readLine().split(" ");
        dp = new boolean[N + 1][15001];
        for(int i = 1 ; i <= N ; i++) {
            weight[i] = Integer.parseInt(lines[i - 1]);
        }
        dfs(0,0);
        K = Integer.parseInt(br.readLine());
        lines = br.readLine().split(" ");
        for(int i = 0 ; i < K ; i++){
            int ball = Integer.parseInt(lines[i]);
            if(ball > 15000) {
                System.out.print("N ");
            }else {
                if(dp[N][ball]){
                    System.out.print("Y ");
                }else{
                    System.out.print("N ");
                }
            }
        }

    }
    static void dfs(int chu, int w){
        if(dp[chu][w]) return;
        dp[chu][w] = true;
        if(chu >= N){
            return;
        }
        dfs(chu + 1, w);
        dfs(chu + 1 , weight[chu + 1] + w);
        dfs(chu + 1 , Math.abs(w - weight[chu + 1]));

    }



}