한 줄 요약
세 문제 모두 같은 본체 (0/1 배낭 + boolean). 답 추출 한 줄만 다르다.
공통 본체
세 문제 다 같은 dp 정의·점화식 쓴다.
상태 정의
dp[i][j] = arr[1..i]까지 봤을 때, 부분수열 합으로 j를 만들 수 있는가 (boolean)
- i: 원소 인덱스 (1..N)
- j: 만들고 싶은 합 (0..S, S = 전체 합)
점화식
dp[i][j] = dp[i-1][j] // i 안 씀
|| (j >= arr[i] && dp[i-1][j - arr[i]]) // i 씀
base / 답 (공통)
base: dp[0][0] = true, 나머지 false
점화식 채운 결과: dp[N][j] (j=0..S)
→ 답 추출만 문제별로 다르다.
문제 1: 부분수열 합 가부
“합이 정확히 K인 부분수열이 존재하는가?”
답: dp[N][K] (true/false)
손 시뮬
입력: arr={2, 2, 1, 5}, K=5
j=0 j=1 j=2 j=3 j=4 j=5
i=0 T F F F F F
i=1 (2) T F T F F F ← {2}
i=2 (2) T F T F T F ← {2,2}=4
i=3 (1) T T T T T T ← {1}, {1,2}, {1,2,2}=5
i=4 (5) T T T T T T ← {5} 추가
답: dp[4][5] = T (“합 5 가능”)
검증: {1,2,2}=5 ✓ 또는 {5} ✓
문제 2: 동일하게 분할
“N개를 두 그룹 A, B로 나눠 합이 같게 만들 수 있는가?” → Yes/No
발상
총합 S라 하자. A 합 = a, B 합 = S − a.
A = B → a = S − a → a = S/2.
즉 “부분수열 합으로 S/2를 만들 수 있는가” — 문제 1과 동일.
예외: S가 홀수면 S/2가 정수가 아니라 즉시 No.
답 추출
java
if (S % 2 != 0) "No";
else if (dp[N][S/2]) "Yes";
else "No";손 시뮬
입력: arr={2, 2, 1, 5}, S=10, S/2=5
위 dp 표 그대로 사용. dp[4][5] = T → “Yes” ✓ (예: {2,2,1} = 5, {5} = 5)
입력 2: arr={4,7,8,9,5}, S=33 → 홀수 → “No” ✓
문제 3: 최소차 분할
“N개를 두 그룹 A, B로 나눠 |A합 − B합|이 최소가 되게”
발상
A 합 = a, B 합 = S − a.
|A − B| = |a − (S − a)| = |2a − S|.
a는 “부분수열 합으로 만들 수 있는 값” — 또 같은 본체.
답 추출
모든 가능한 a (= dp[N][a] = true인 a) 중에서
|2a - S| 최솟값 출력
java
int ans = Integer.MAX_VALUE;
for (int a = 1; a < S; a++) { // a=0과 a=S는 한쪽 공집합 → 보통 제외
if (dp[N][a]) {
ans = Math.min(ans, Math.abs(2*a - S));
}
}손 시뮬
입력: arr={2, 2, 1, 5}, S=10
위 dp 표에서 dp[4][a]=T인 a: 0, 1, 2, 3, 4, 5
(j=6~10도 추가로 채우면 6, 7, 8, 10도 true)
a: 0 1 2 3 4 5 ...
|2a-10|: 10 8 6 4 2 0 ... ← a=5에서 0
답: 0 ✓ (A={2,2,1}=5, B={5}=5)
자료형 / 복잡도
| 항목 | 값 |
|---|---|
| dp 크기 | [N+1][S+1] |
| dp 타입 | boolean |
| 시간 | O(N × S) |
| N, 원소값 제약 | 보통 N ≤ 100, 원소 ≤ 1000 → S ≤ 10⁵ |
1D 압축 (0/1 골격이라 역방향)
java
boolean[] dp = new boolean[S+1];
dp[0] = true;
for (int i = 1; i <= N; i++) {
for (int j = S; j >= arr[i]; j--) { // 역방향
dp[j] = dp[j] || dp[j - arr[i]];
}
}왜 역방향?: 윗 행(이번 i 안 더해진 값) 참조해야 0/1 본질 유지. 정방향 가면 같은 원소 여러 번 쓰는 무한 배낭이 됨.
|= 관용형 (선호 시)
java
dp[j] |= dp[j - arr[i]];if문 직관형 = if (dp[j-arr[i]]) dp[j] = true; 동일. 본인 취향대로.
답 추출 한 줄로 비교
| 문제 | 답 추출 |
|---|---|
| 부분수열 합 가부 | dp[N][K] |
| 동일하게 분할 | S%2==0 && dp[N][S/2] |
| 최소차 분할 | min over a (|2a-S|) where dp[N][a] |
본체는 같다. dp 표를 한 번 채운 뒤 답 추출만 갈아끼우면 세 문제가 풀린다.
막힐 때 자가 진단
1. dp 정의가 boolean인지 확인
“어떤 합이 가능한가?” → boolean
”어떤 합을 만드는 가짓수?” → int + (가짓수 변형 노트)
“어떤 합의 최댓값?” → int + max + 가치 (배낭 노트)
세 다른 문제. boolean 골격에서 가짓수나 max 끼면 본체 망가짐.
2. base는 dp[0][0]만
“원소 0개로 합 0 만드는 게 1가지” → dp[0][0] = true
나머지 dp[0][j>0] = false (원소 없는데 양수 합 못 만듦)
3. 답 추출 범위
최소차 분할에서 a=0과 a=S 포함 여부 확인
보통 “각 그룹 최소 1개”라 a=1..S-1만
함정 모음
함정 1: 동일하게 분할에서 홀수 S 누락
S=33 (홀수) → S/2 = 16.5 → 정수 아님 → 무조건 No.
코드에서 S/2 정수 나눗셈이라 16 나옴 → dp[N][16] 검사 → false → No 출력 (우연히 맞음).
하지만 명시적 검사가 안전:
java
if (S % 2 != 0) { System.out.println("No"); return; }함정 2: 최소차 분할 답 추출 범위
for (a = 0; a <= S; a++) 돌리면 a=0 (A 공집합)도 후보. |2·0 − S| = S → 보통 최솟값 아님이라 자동 탈락하지만, N=1 같은 경계에서 잘못된 답.
각 그룹 ≥ 1개 명시:
java
for (int a = 1; a < S; a++) ...함정 3: 0/1인데 1D 정방향
java
for (int j = arr[i]; j <= S; j++) // 정방향 — 무한 배낭!
dp[j] |= dp[j - arr[i]];이러면 같은 원소 여러 번 사용. 부분수열 합 의미 깨짐. 반드시 역방향.
한 줄 정착 카드
세 문제 같은 본체:
dp[i][j] = "i까지 봤을 때 합 j 가능?" (boolean)
점화식 = dp[i-1][j] || dp[i-1][j-arr[i]]
답 추출만 다름:
부분수열 합 가부 → dp[N][K]
동일하게 분할 → S 짝수 && dp[N][S/2]
최소차 분할 → min |2a-S| where dp[N][a]