[백준] 2629 양팔저울 [JAVA]

문제링크 : www.acmicpc.net/problem/2629

2629번: 양팔저울

 추의 무게는 500g 이하이고 개수는 30개 이하이므로 추를 가지고 셀 수 있는 무개의 최대 g은 15000이다.

확인하려는 무게는 40000g 이하이므로 15000g 초과에 대해서는 N일 것이다.

구슬이 항상 왼쪽에 있다고 가정할 때 추를 올리는 방법은 왼쪽에 올리거나 오른쪽에 올리거나 올리지 않는 것이다.

bottom-up 방식으로 풀었으며 어떤 무게 x가 가능할 때 i번째 추를 가지고 무게를 잴 수 있는 방법은 i번 추를 왼쪽에 올리는 경우, 오른쪽에 올리는 경우, i번 추 빼고 모두 한쪽으로 옮기는 경우로 생각했다. 

import java.io.*;
import java.util.*;
public class Main {
	public static int N;
	public static int ball[];
	public static boolean isAvail[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		ball = new int[N+1];
		isAvail = new boolean[40001];
		StringTokenizer st=  new StringTokenizer(br.readLine());
		for(int i=1;i<=N;i++) {
			ball[i] = Integer.parseInt(st.nextToken());
		}
		
		//조합
		for(int i=1;i<=N;i++) {
			ArrayList<Integer> temp = new ArrayList<Integer>();
			temp.add(ball[i]);
			for(int j=1;j<=15000;j++) {
				if(isAvail[j]) {
					if(ball[i]-j > 0) {
						temp.add(ball[i]-j);
					}
					if(ball[i]+j <= 15000) {
						temp.add(ball[i]+j);
					}
					if(j-ball[i] > 0) {
						temp.add(j-ball[i]);
					}
				}
			}
			for(int j=0;j<temp.size();j++) {
				isAvail[temp.get(j)] = true;
			}
		}
	
		//결과
		int query = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<query;i++) {
			int q = Integer.parseInt(st.nextToken());
			if(isAvail[q]==true) {
				System.out.println("Y");
			}else {
				System.out.println("N");
			}
		}
	}

}