문제 설명

전략

• 구슬의 무게를 확인하는 것은 총 2가지 방법으로 가능하다

  1. 한 쪽에 추만 올라가고 그 무게가 구슬과 같을 때
  2. 추와 구슬이 같이 올라가고 그 무게가 추들의 무게와 같을 때

• 추를 올릴 때 마다 DFS를 통한 가지치기로 값을 구하려고 했는 데 dfs재귀를 돌리는 경우는 총 3가지 이다

		dfs(depth + 1, now + choo[depth]); // 1번 case 현재 구슬 + 이번 추를 구슬 쪽에
		dfs(depth + 1, now - choo[depth]); // 2번 case 구슬만 저울에 vs 이번 추를 반대쪽에
		dfs(depth + 1, now); // 3번 이번 추를 올리지 않기

• 현재 추까지 왔을 때 같은 무게가 발생하면 중복이 발생한 것으로 가지치기를 해준다

• 모든 추를 다 확인했을 때 가능한 모든 경우의 수를 Set에 담아서 해당 구슬 무게가 Set에 있는 지 확인한다

정답코드

package algorithms;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class DoubleArmScales {

	static int N;
	static int M;
	static int[] choo;
	static int[] marble;
	static boolean[][] visited;
	static StringBuilder sb = new StringBuilder();
	static Set<Integer> chooSet;
	static int sum = 0;


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		//input --------------------------------------
		N = Integer.parseInt(st.nextToken());
		choo = new int[N];
		chooSet = new HashSet<>();
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int now = Integer.parseInt(st.nextToken());
			choo[i] = now;
			sum += now;
		}

		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		marble = new int[M];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M ; i++) {
			marble[i] = Integer.parseInt(st.nextToken());
		}
		//input --------------------------------------
		
		visited = new boolean[N+1][sum+1];
		
		dfs(0,0);
		
		for (int i = 0; i < M ; i++) {
			if(chooSet.contains(marble[i]))sb.append("Y ");
			else sb.append("N ");
		}
		
		System.out.println(sb);
	}

	public static void dfs(int depth, int now) {
		
		//가능한 모든 추 무게들을 set에 넣어둔다
		chooSet.add(Math.abs(now));
		
		if (depth == N)return;
		
		//각각의 depth마다 같은 무게의 추가 들어오면 가지치기 
		if(visited[depth][Math.abs(now)])return;
		
		visited[depth][Math.abs(now)] = true;
		
		dfs(depth + 1, now + choo[depth]); // 1번 case 현재 구슬 + 이번 추를 구슬 쪽에
		dfs(depth + 1, now - choo[depth]); // 2번 case 구슬만 저울에 vs 이번 추를 반대쪽에
		dfs(depth + 1, now); // 3번 이번 추를 올리지 않기
		
		return;
	}
}