• 3개의 선택지(왼쪽, 오른쪽, 안 올림)로 재귀를 돌린다면 ${3^{30}}$ 이므로 시간 초과가 발생한다 $~$$~$ memoization 필요
  • [idx][left][right]를 하게 되면 ${30 \times 15000 \times 15000}$ 이 되어 메모리 낭비일 뿐더러 메모리 초과이다. 따라서, [idx][weight]로 하되, left는 양수, right는 음수로 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53



import java.io.*;
import java.util.*;

public class Main {
	static final int OFFSET = 15010; // 추 30(개) x 500(g) = 15000
	static int N, M;
	static int[] weight = new int[35];
	static boolean[][] memo = new boolean[35][OFFSET * 2];

	static void go(int idx, int curWeight) {
		if (memo[idx][curWeight]) return;
		memo[idx][curWeight] = true;

		if (idx >= N) return; // idx가 N 이상인지 여기서 체크해야 한다

		go(idx + 1, curWeight + weight[idx+1]); // 왼쪽 
		go(idx + 1, curWeight - weight[idx+1]); // 오른쪽
		go(idx + 1, curWeight); // 안 올림
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in 
			= new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int weightSum = 0;
		for (int i = 1; i <= N; i++) {
			weight[i] = Integer.parseInt(st.nextToken());
			weightSum += weight[i];
		}

		go(0, OFFSET);

		M = Integer.parseInt(in.readLine());
		st = new StringTokenizer(in.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) {
			int input = Integer.parseInt(st.nextToken());
			String res = "N";
			if (input <= weightSum) { // 최대 나올 수 있는 값보다 크면 skip
				for (int j = 1; j <= N; j++) {
					if (memo[j][OFFSET + input]) {
						res = "Y";
						break;
					}
				}
			}
			sb.append(res).append(" ");
		}
		System.out.println(sb);
	}
}