문제
최대 30개의 추가 있고, 각 추의 무게는 최대 500이다. 이 추들을 이용하여 양팔저울로 달 수 있는 무게를 판별한다. 여러 개의 구슬 무게가 주어질 때, 각각 달 수 있는지 여부를 출력한다.
입력
첫째 줄에 추의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄에 N개 추의 무게가 주어진다(각 무게 1 ≤ w ≤ 500). 셋째 줄에 구슬의 개수 M(1 ≤ M ≤ 7), 넷째 줄에 M개 구슬의 무게가 주어진다(각 무게 1 ≤ w ≤ 40,000).
출력
각 구슬의 무게를 달 수 있으면 Y, 없으면 N을 공백으로 구분하여 출력한다.
예제
입력
2
1 4
2
3 2출력
Y Y풀이
핵심 아이디어: dp[i][w]를 "i번째 추까지 사용했을 때 무게 w를 만들 수 있는가"로 정의한다. 추를 하나씩 추가할 때마다 세 가지 선택이 있다: ① 이 추를 사용하지 않는다, ② 이 추를 구슬과 같은 쪽에 올린다(무게 차이 |w - arr[i]|), ③ 이 추를 반대쪽에 올린다(무게 합 w + arr[i]).
dp[i][w] = true이면 추 i개로 무게 w를 만들 수 있음을 의미한다.- 초기 상태:
dp[0][0] = true. - 재귀적으로 세 가지 전이를 적용한다:
dp[idx+1][weight]— 현재 추를 사용하지 않음dp[idx+1][weight + arr[idx+1]]— 추를 반대쪽에 올림dp[idx+1][|weight - arr[idx+1]|]— 추를 같은 쪽에 올림
- 이미 방문한 상태는 재귀 호출을 건너뛰어 중복 계산을 방지한다.
- 구슬 무게가 15,000을 초과하면 무조건 N, 아니면
dp[N][question]으로 판단한다.
추의 무게 합이 최대 15,000이므로 배열 크기를 15,001로 설정하면 충분하다.
코드
import java.io.*;
import java.util.*;
public class Day360BOJ2629양팔저울 {
static int N, M, question, max = 15000, arr[];
static boolean dp[][];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N + 1];
dp = new boolean[31][max + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
recur(0, 0);
StringBuilder sb = new StringBuilder();
M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
question = Integer.parseInt(st.nextToken());
if (question > 15000)
sb.append("N ");
else
sb.append(dp[N][question] ? "Y " : "N ");
}
System.out.println(sb);
br.close();
}
public static void recur(int idx, int weight) {
if (dp[idx][weight])
return;
dp[idx][weight] = true;
if (idx == N)
return;
recur(idx + 1, weight + arr[idx + 1]);
recur(idx + 1, weight);
recur(idx + 1, Math.abs(weight - arr[idx + 1]));
}
}복잡도
- 시간: O(N·W) — N개의 추, W = 15,000 (최대 무게 합)
- 공간: O(N·W) — DP 테이블