한 줄 요약
둘은 같은 본체. 원소 재사용 여부가 점화식에서 “윗 행 vs 같은 행” 한 글자 차이로 갈린다.
본체
각 원소를 쓸까 말까 (또는 무한이면 몇 번 쓸까) 결정하면서, 용량 j까지 채울 때의 최댓값.
상태 정의
dp[i][j] = i번째 원소까지 봤을 때, 용량 j 이하에서 만들 수 있는 최대 가치
- i: 원소 인덱스 (1..N)
- j: 용량 (0..C)
- 값: 최대 가치
점화식
dp[i][j] = max(
dp[i-1][j], // i 안 씀
dp[?][j - w[i]] + v[i] // i 씀
)
?가 i-1인지 i인지가 0/1 ↔ 무한의 차이.
| 유형 | 재사용? | “i 씀” 항 | 의미 |
|---|---|---|---|
| 0/1 | 불가 | dp[i-1][j-w[i]] + v[i] | i를 한 번 쓰고 끝 |
| 무한 | 가능 | dp[i][j-w[i]] + v[i] | i를 또 쓸 수 있어 같은 행 참조 |
1D 압축
2D dp[i][j]를 dp[j] 한 줄로 압축할 수 있다.
핵심 규칙
점화식 우변 인덱스가 좌변보다 먼저 채워지는 방향으로 루프를 돌린다.
- 0/1: 윗 행(i-1) 참조 → 한 줄에서는 j 큰 쪽이 아직 안 덮여 있어야 → 역방향
- 무한: 같은 행(i) 참조 → j 작은 쪽이 미리 갱신돼 있어야 → 정방향
0/1 1D (역방향)
java
int[] dp = new int[C+1];
for (int i = 1; i <= N; i++) {
for (int j = C; j >= w[i]; j--) { // 역방향
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}왜 역방향?: j 큰 쪽부터 갱신 → dp[j-w[i]]는 아직 “윗 행” 값(이번 i 안 더해진 값). 이게 0/1의 본질.
무한 1D (정방향)
java
int[] dp = new int[C+1];
for (int i = 1; i <= N; i++) {
for (int j = w[i]; j <= C; j++) { // 정방향
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}왜 정방향?: j 작은 쪽부터 갱신 → dp[j-w[i]]는 이미 “이번 i”가 더해진 값. 그래서 같은 i를 또 쓰는 효과.
손 시뮬 — 0/1 배낭
입력: N=3, C=7
원소: w={3, 4, 2}, v={4, 5, 3}
j=0 j=1 j=2 j=3 j=4 j=5 j=6 j=7
i=0 0 0 0 0 0 0 0 0 ← base
i=1 (w=3, 0 0 0 4 4 4 4 4 ← j>=3부터 원소1 사용 가능
v=4)
i=2 (w=4, 0 0 0 4 5 5 5 9 ← j=7에서 원소1+원소2 (4+5)
v=5)
i=3 (w=2, 0 0 3 4 5 7 8 9 ← j=2부터 원소3 사용 가능
v=3)
답: dp[3][7] = 9
검증: 원소 1(w=3,v=4) + 원소 2(w=4,v=5) = 무게 7, 가치 9. ✓
dp[3][5] 계산 따라가기
dp[3][5] = max(
dp[2][5], // 원소 3 안 씀
dp[2][5-2] + 3 // 원소 3 씀 (w=2)
) = max(5, dp[2][3] + 3)
= max(5, 4 + 3)
= max(5, 7) = 7
윗 행만 참조 ✓ (0/1의 본질)
손 시뮬 — 무한 배낭
입력: N=2, C=7
원소: w={3, 4}, v={4, 5}
j=0 j=1 j=2 j=3 j=4 j=5 j=6 j=7
i=0 0 0 0 0 0 0 0 0
i=1 (w=3, 0 0 0 4 4 4 8 8 ← j=6에서 원소1 두 번! (4+4)
v=4)
i=2 (w=4, 0 0 0 4 5 5 8 9 ← j=7에서 원소1+원소2 (4+5)
v=5)
답: dp[2][7] = 9
dp[1][6] 계산 (무한의 핵심)
dp[1][6] = max(
dp[0][6], // 원소 1 안 씀
dp[1][6-3] + 4 // 원소 1 씀 — 같은 행 참조!
) = max(0, dp[1][3] + 4)
= max(0, 4 + 4)
= max(0, 8) = 8
dp[1][3]을 참조 → 같은 i 행에서 이미 원소 1 한 번 쓴 결과를 다시 참조 → 원소 1을 두 번 쓴 셈.
0/1이었으면 dp[0][3]=0을 봤을 거고 답이 4였을 거다.
Base / Sentinel / 답 추출
| 항목 | 값 |
|---|---|
| base | dp[0][0..C] = 0 (원소 0개면 가치 0) |
| sentinel | 없음 (도달 불가 상태 없음) |
| 답 | dp[N][C] |
예외: “용량 정확히 j” 변형은 sentinel 필요. 위는 “용량 이하”라서 0이 안전 base.
자주 만나는 변형
변형 1: 부분수열 합 (가부)
“어떤 부분수열 합이 정확히 K인가?”
같은 골격, dp 값이 boolean.
dp[i][j] = dp[i-1][j] || dp[i-1][j - arr[i]]
dp[0][0] = true
답: dp[N][K]
0/1 배낭의 본체 + boolean. 동일하게 분할, 최소차 분할이 다 이 변형.
변형 2: 부분집합 합 가짓수
“합이 정확히 K가 되는 부분집합 개수”
boolean → int, OR → +.
dp[i][j] = dp[i-1][j] + dp[i-1][j - arr[i]]
dp[0][0] = 1 (공집합 1가지)
가짓수 DP의 깔끔한 형태.
변형 3: 무한 배낭 — 동전 거슬러주기
“금액 M을 만드는 동전 최소 개수”
같은 무한 배낭 골격, max → min.
dp[j] = min(dp[j], dp[j - coin] + 1)
dp[0] = 0, 나머지 sentinel (예: M+1)
손 시뮬 — 부분수열 합 (변형 1)
입력: 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 ← base
i=1 (2) T F T F F F ← {2} 가능
i=2 (2) T F T F T F ← {2,2} 가능
i=3 (1) T T T T T T ← {1}, {1,2}, {1,2,2} 가능
i=4 (5) T T T T T T ← {5} 가능
답: dp[4][5] = T → “합 5 가능”
검증: {1, 2, 2} → 1+2+2=5 ✓, 또는 {5} ✓
손 시뮬 — 부분집합 합 가짓수 (변형 2)
입력: arr={1, 2, 3}, K=3
j=0 j=1 j=2 j=3
i=0 1 0 0 0 ← base (공집합 1가지)
i=1 (1) 1 1 0 0 ← {1} 추가
i=2 (2) 1 1 1 1 ← {2}, {1,2} 추가
i=3 (3) 1 1 1 2 ← {3}, {1,2} 두 가지
답: dp[3][3] = 2
검증: 합 3을 만드는 부분집합 = {3}, {1,2} → 2가지 ✓
막힐 때 자가 진단 (3분 체크)
1. 어느 유형인지부터
“원소를 여러 번 쓸 수 있는가?”
Yes → 무한 배낭 (정방향)
No → 0/1 배낭 (역방향)
2. dp 정의 한국어로 적기
“dp[i][j] = ___까지 봤을 때, ___일 때, ___ 최대”
3개 빈칸 다 적었나? 적었으면 점화식이 자동으로 따라온다.
3. 손 시뮬 (N=3 정도)
5×5 표 손으로 채워서 답 맞나 확인. 30초.
함정 모음
함정 1: 1D 압축 시 루프 방향
java
for (int j = w[i]; j <= C; j++) // 정방향 = 무한
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);이건 무한 배낭 1D. 0/1 배낭이면 for (j = C; j >= w[i]; j--) 역방향.
→ 외울 게 아니라, “윗 행 참조 vs 같은 행 참조” 떠올리면 자동.
함정 2: 2D에서 “안 씀” 항 누락
java
for (int j = w[i]; j <= C; j++)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);j < w[i]에서 dp[i][j]가 그대로 0이 됨. 이전 행 가치 누적이 끊긴다.
수정:
java
for (int j = 0; j <= C; j++) {
dp[i][j] = dp[i-1][j]; // 먼저 "안 씀" 깔기
if (j >= w[i]) {
dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
}
}1D는 이게 자동 처리됨 (덮어쓰기 안 하면 그대로) — 1D의 장점.
한 줄 정착 카드
0/1 → 못 재사용 → 윗 행 참조 → 1D 역방향 → max
무한 → 재사용 OK → 같은 행 참조 → 1D 정방향 → max
부분합 가부 → boolean, OR
부분합 가짓수 → int, +, base=1
동전 최소 → min, sentinel=큰 값, base=0