BJ2629 양팔저울

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

재귀함수로 30개의 추를 (좌, 우, 사용하지 않음)을 모두 계산하면 3^30의 호출을 해야 한다.

중복된 계산을 제외하면서 빠르게 계산하기 위해, 이전에 나온 값을 boolean[] 배열 인덱스를 활용해 담아두고, 가능한 값을 추가하여 해결한다.

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

public class BJ2629 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static boolean[] b  = new boolean[15001], dp = new boolean[15001];
	static int[] choos;
	static int N, M;

	
	static void makeB() {
		dp[0] = true;
		b[0] = true;
		int left, right;
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j <= 15000 ; j++)
				if(b[j]) {
					left = Math.abs(choos[i] - j);
					right = Math.abs(choos[i] + j);
					dp[left] = true;
					dp[right] = true;
					dp[choos[i]] = true;
				}
			for(int j = 0 ; j <= 15000 ; j++) {
				b[j] = dp[j];
			}
		}
	}

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine()); // 추 갯수를 입력받는다.
		choos = new int[N]; // 메모리 할당.
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) { // 추들을 배열에 저장.
			choos[i] = Integer.parseInt(st.nextToken());
		}

		makeB();
		
		M = Integer.parseInt(br.readLine()); // 테스트할 구슬의 갯수.
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) { // 위에서 만들어둔 boolean 배열에 맞게 출력한다.
			int tmp = Integer.parseInt(st.nextToken());
			if (tmp <= 15000 && dp[tmp])
				bw.append("Y" + " ");
			else
				bw.append("N" + " ");
		}
		bw.flush();
	}
}