📌 문제 정보
- 번호: 1006
- 제목: 습격자 초라기
- 난이도: Platinum 3
- 분류: 다이나믹 프로그래밍
📝 문제 요약
원형 도넛 모양 진영(외각 N, 내각 N, 총 2N칸)을 점령하는 데 필요한 최소 소대 수 구하기. 한 소대는 한 칸 또는 인접한 두 칸을 동시 점령 가능 (단, 두 칸 적군 합 ≤ W)
💡 접근 방식
직선이면 4상태 1D DP로 풀리지만, 원형이라 1번-N번 진영이 인접해서 처음과 끝이 페어로 묶일 수 있음. 처음엔 그리디로 시도하다가 반례를 떠올리고 DP로 선회. 원형 처리는 시작/끝 상태를 4가지로 미리 강제하고 각각 DP를 돌린 뒤 최솟값 취하는 케이스 분할로 해결
🔹 1단계 – 상태 정의 (한 진영 = 한 열)
각 진영 i를 외각/내각 두 칸이 쌓인 "열"로 보고, 이번 열을 어떻게 채웠는지를 4가지 상태로 표현
| 상태 | 외각 | 내각 | 의미 |
|---|---|---|---|
| 0 | ✓ | ✓ | 깔끔하게 끝남 |
| 1 | ✗ | ✓ | 외각 미커버 (다음 열 외각과 페어 예약) |
| 2 | ✓ | ✗ | 내각 미커버 (다음 열 내각과 페어 예약) |
| 3 | ✗ | ✗ | 둘 다 미커버 (다음 열과 페어 예약) |
dp[i][s] = i번 진영까지 처리 시 상태 s가 되는 데 필요한 최소 소대 수
🔹 2단계 – 전이 (i → i+1)
이전 상태에 따라 이번 열에서 할 수 있는 일이 달라짐
이전 상태 0 → 이번 열 자유 (5가지 분기)
- 외/내 솔로 2팀 → 상태 0, +2
- 외+내 세로 페어 → 상태 0, +1 (조건: 외+내 ≤ W)
- 외 솔로, 내 미루기 → 상태 1, +1
- 내 솔로, 외 미루기 → 상태 2, +1
- 둘 다 미루기 → 상태 3, +0
이전 상태 1 → 외각 가로 페어 강제 (조건: 이전 외 + 이번 외 ≤ W)
- 내 솔로 → 상태 0, +2
- 내 미루기 → 상태 2, +1
이전 상태 2 → 대칭
이전 상태 3 → 외/내 가로 페어 둘 다 강제
- 무조건 상태 0, +2🔹 3단계 – 원형 처리 (4 케이스 분할)
도넛이라 1번-N번도 인접. 1번-N번 사이의 페어 여부에 따라 시나리오 4가지
| 케이스 | 외각 원형 페어 | 내각 원형 페어 | 시작 dp[0] | 답 |
|---|---|---|---|---|
| 1 | ✗ | ✗ | (자유) | dp[N-1][0] |
| 2 | ✗ | ✓ | (1, 0, ∞, ∞) | dp[N-1][2] + 1 |
| 3 | ✓ | ✗ | (1, ∞, 0, ∞) | dp[N-1][1] + 1 |
| 4 | ✓ | ✓ | (0, ∞, ∞, ∞) | dp[N-1][3] + 2 |
각 케이스마다 DP를 따로 돌리고, 4개 결과 중 최솟값이 답
예시 (N=4, W=5)
외각: 3 5 5 2
내각: 5 5 5 5- 케이스 1 (페어 없음): 외각 합 페어 불가능, 내각 합 페어 불가능 → 모두 솔로 → 8소대
- 케이스 3 (외각 원형 페어): 3+2=5 ≤ 5 ✓ → (외[0], 외[3]) 1소대 + 나머지 6소대 → 7소대 ← 최솟값
🔹 4단계 – 예외 (N=1)
진영이 1개면 i+1이 없어 DP가 안 돌아감. 별도 처리
if (N == 1) return (inner[0] + outer[0] <= W) ? 1 : 2;💻 핵심 코드
static int solve() {
if (N == 1) return (inner[0] + outer[0] <= W) ? 1 : 2;
int ans = INF;
// 케이스 1: 원형 묶음 없음
int s0 = (inner[0] + outer[0] <= W) ? 1 : 2;
int[][] dp1 = runDp(s0, 1, 1, 0);
ans = Math.min(ans, dp1[N - 1][0]);
// 케이스 2: inner 원형 페어
if (inner[0] + inner[N - 1] <= W) {
int[][] dp2 = runDp(1, 0, INF, INF);
ans = Math.min(ans, dp2[N - 1][2] + 1);
}
// 케이스 3: outer 원형 페어
if (outer[0] + outer[N - 1] <= W) {
int[][] dp3 = runDp(1, INF, 0, INF);
ans = Math.min(ans, dp3[N - 1][1] + 1);
}
// 케이스 4: 둘 다 원형 페어
if (inner[0] + inner[N - 1] <= W && outer[0] + outer[N - 1] <= W) {
int[][] dp4 = runDp(0, INF, INF, INF);
ans = Math.min(ans, dp4[N - 1][3] + 2);
}
return ans;
}
static int[][] runDp(int s0, int s1, int s2, int s3) {
int[][] dp = new int[N][4];
for (int i = 0; i < N; i++)
dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = INF;
dp[0][0] = s0; dp[0][1] = s1; dp[0][2] = s2; dp[0][3] = s3;
for (int i = 0; i < N - 1; i++) {
int j = i + 1, v;
v = dp[i][0];
if (v < INF) {
if (inner[j] + outer[j] <= W && v + 1 < dp[j][0]) dp[j][0] = v + 1;
if (v + 2 < dp[j][0]) dp[j][0] = v + 2;
if (v + 1 < dp[j][1]) dp[j][1] = v + 1;
if (v + 1 < dp[j][2]) dp[j][2] = v + 1;
if (v < dp[j][3]) dp[j][3] = v;
}
v = dp[i][1];
if (v < INF && outer[i] + outer[j] <= W) {
if (v + 2 < dp[j][0]) dp[j][0] = v + 2;
if (v + 1 < dp[j][2]) dp[j][2] = v + 1;
}
v = dp[i][2];
if (v < INF && inner[i] + inner[j] <= W) {
if (v + 2 < dp[j][0]) dp[j][0] = v + 2;
if (v + 1 < dp[j][1]) dp[j][1] = v + 1;
}
v = dp[i][3];
if (v < INF && inner[i] + inner[j] <= W && outer[i] + outer[j] <= W) {
if (v + 2 < dp[j][0]) dp[j][0] = v + 2;
}
}
return dp;
}⏳ 복잡도 분석
- 시간 복잡도:
O(N)- 4 케이스 × N개 진영 × 상수 전이 = O(4N) = O(N)
- 공간 복잡도:
O(N)- dp 배열 N×4 (케이스마다 새로 할당하지만 상수 배수)
⚠️ 어려웠던 점
- 원형이라는 점이 가장 까다로웠습니다. 일반 1D DP로는 1번-N번 페어를 표현할 수 없어서 시작/끝 상태를 4가지로 강제하는 케이스 분할이 필요하다는 점이 어려웠습니다.
📄 전체 코드
package rtaeho.week04.B1006;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static final int INF = 1 << 29;
static int N, W;
static int[] inner, outer;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine().trim());
while (T-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
inner = new int[N];
outer = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
inner[i] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
outer[i] = Integer.parseInt(st.nextToken());
sb.append(solve()).append('\n');
}
System.out.print(sb);
}
static int solve() {
if (N == 1) {
return (inner[0] + outer[0] <= W) ? 1 : 2;
}
int ans = INF;
// 케이스 1: 원형 묶음 없음
int s0 = (inner[0] + outer[0] <= W) ? 1 : 2;
int[][] dp1 = runDp(s0, 1, 1, 0);
ans = Math.min(ans, dp1[N - 1][0]);
// 케이스 2: inner[0] - inner[N-1] 원형 묶음
if (inner[0] + inner[N - 1] <= W) {
int[][] dp2 = runDp(1, 0, INF, INF);
ans = Math.min(ans, dp2[N - 1][2] + 1);
}
// 케이스 3: outer[0] - outer[N-1] 원형 묶음
if (outer[0] + outer[N - 1] <= W) {
int[][] dp3 = runDp(1, INF, 0, INF);
ans = Math.min(ans, dp3[N - 1][1] + 1);
}
// 케이스 4: 둘 다 원형 묶음
if (inner[0] + inner[N - 1] <= W && outer[0] + outer[N - 1] <= W) {
int[][] dp4 = runDp(0, INF, INF, INF);
ans = Math.min(ans, dp4[N - 1][3] + 2);
}
return ans;
}
static int[][] runDp(int s0, int s1, int s2, int s3) {
int[][] dp = new int[N][4];
for (int i = 0; i < N; i++) {
dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = INF;
}
dp[0][0] = s0;
dp[0][1] = s1;
dp[0][2] = s2;
dp[0][3] = s3;
for (int i = 0; i < N - 1; i++) {
int j = i + 1;
int v;
// state 0: i열 둘 다 커버
v = dp[i][0];
if (v < INF) {
if (inner[j] + outer[j] <= W && v + 1 < dp[j][0])
dp[j][0] = v + 1;
if (v + 2 < dp[j][0])
dp[j][0] = v + 2;
if (v + 1 < dp[j][1])
dp[j][1] = v + 1;
if (v + 1 < dp[j][2])
dp[j][2] = v + 1;
if (v < dp[j][3])
dp[j][3] = v;
}
// state 1: outer[i] 미커버 → outer[j]와 가로 묶음 필수
v = dp[i][1];
if (v < INF && outer[i] + outer[j] <= W) {
if (v + 2 < dp[j][0])
dp[j][0] = v + 2;
if (v + 1 < dp[j][2])
dp[j][2] = v + 1;
}
// state 2: inner[i] 미커버 → inner[j]와 가로 묶음 필수
v = dp[i][2];
if (v < INF && inner[i] + inner[j] <= W) {
if (v + 2 < dp[j][0])
dp[j][0] = v + 2;
if (v + 1 < dp[j][1])
dp[j][1] = v + 1;
}
// state 3: 둘 다 미커버
v = dp[i][3];
if (v < INF && inner[i] + inner[j] <= W && outer[i] + outer[j] <= W) {
if (v + 2 < dp[j][0])
dp[j][0] = v + 2;
}
}
return dp;
}
}