첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다.
둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다.
같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있다.
세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다.
네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.
주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다.
출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.
무게를 확인해야하는 구슬이 항상 왼쪽에 있다고 가정하면 항상 아래 3가지의 경우 중 하나로 나타난다.
- 구슬을 왼쪽에 추가 (w+weights[i])
- 구슬을 오른쪽에 추가 (|w-weights[i]|)
- 올리지 않음 (w)
이 경우의 수를 가지고 for문을 돌려서 해결해도 되지만
나는 재귀를 이용했다.
이 문제에서 주의해야하는 점은
추의 무게는 500g이하, 갯수는 30개 이하이므로 추를 가지고 셀 수 있는 무게는 최대 15000g이다.
확인하려는 무게는 40000g 이하이므로 15000g 초과에 대해서는 확인하지않아도 결과값이 N
이다.
즉, dp 배열에 대해서 15000까지만 확인하면 불필요한 연산을 줄일 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[] weights;
static boolean[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
weights = new int[N];
dp = new boolean[N+1][15001];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
weights[i] = Integer.parseInt(st.nextToken());
}
findDP(0, 0);
M = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int num = Integer.parseInt(st.nextToken());
if(num > 15000) sb.append("N ");
else sb.append(dp[N][num] ? "Y " : "N ");
}
System.out.println(sb);
}
static void findDP(int n, int w) {
if(dp[n][w]) return;
dp[n][w] = true;
if(n == N) return;
findDP(n + 1, w + weights[n]);
findDP(n + 1, w);
findDP(n + 1, Math.abs(w - weights[n]));
}
}