습격자 초라기

---

🔗 🔗 전체 1006번 문제

조건

---

문제

---

초라기는 한국의 비밀국방기지(원타곤)를 습격하라는 임무를 받은 특급요원이다. 원타곤의 건물은 도넛 형태이며, 초라기는 효율적인 타격 포인트를 정하기 위해 구역을 아래와 같이 두 개의 원 모양으로 나누었다. (그림의 숫자는 각 구역의 번호이다.)

초라기는 각각 $W$명으로 구성된 특수소대를 다수 출동시켜 모든 구역에 침투시킬 예정이며, 각 구역 별로 적이 몇 명씩 배치되어 있는지는 초라기가 모두 알고 있다. 특수소대를 아래 조건에 따라 침투 시킬 수 있다.

1. 한 특수소대는 침투한 구역 외에, 인접한 한 구역 더 침투할 수 있다. (같은 경계를 공유하고 있으면 인접 하다고 한다. 위 그림에서 1구역은 2, 8, 9 구역과 서로 인접한 상태다.) 즉, 한 특수소대는 한 개 혹은 두 개의 구역을 커버할 수 있다.
2. 특수소대끼리는 아군인지 적인지 구분을 못 하기 때문에, 각 구역은 하나의 소대로만 커버해야 한다.
3. 한 특수소대가 커버하는 구역의 적들의 합은 특수소대원 수 $W$ 보다 작거나 같아야 한다.

이때 초라기는 원타곤의 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 알고 싶어 한다.

입력

---

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

첫째 줄에는 (구역의 개수)/2 값 $N$과 특수 소대원의 수 $W$가 주어진다. ($1 ≤ N ≤ 10000$, $1 ≤ W ≤ 10000$).

둘째 줄에는 $1 ~ N$번째 구역에 배치된 적의 수가 주어지고, 셋째 줄에는 $N + 1 ~ 2N$번째 구역에 배치된 적의 수가 공백으로 구분되어 주어진다. (1 ≤ 각 구역에 배치된 최대 적의 수 ≤ 10000) 단, 한 구역에서 특수 소대원의 수보다 많은 적이 배치된 구역은 존재하지 않는다. (따라서, 각 구역에 배치된 최대 적의 수 ≤ $W$)

출력

---

각 테스트케이스에 대해서 한 줄에 하나씩 원타곤의 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 출력하시오.

케이스

---

예제 1

---

• 입력

TC
1
2
3
4
1
8 100
70 60 55 43 57 60 44 50
58 40 47 90 45 52 80 40

• 출력

TC
1
11

힌트

---

하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소대를 침투시켜야 한다.

풀이

---

백준 알고리즘을 순서대로 푸는 나 같은 초심자들에게 힘의 차이를 느끼게 해주는 문제라고 한다. 🔗 solved.ac에 의하면 문제 등급이 무려 PLATINUM III 수준. 지금까지 푼 문제 중 가장 높은 등급이 🔗 ACM Craft (GOLD III) 수준임을 감안하면 월등히 높은 수준의 문제. 실제로 풀면서도 혼자서는 도저히 방법이 안 떠오르는데다, 풀이를 봐도 이해가 잘 안 됐다.

해당 문제에 주어지는 구역은 원형이다. 문제를 쉽게 접근하기 위해선 이 원형을 임의로 잘라 직사각형 형태로 전개해야 한다. 즉, 풀 때는 직사각형 형태지만, 실제로는 원형이므로 직사각형의 잘린 양 끝부분까지 염두하여 계산을 해야한다. 난이도를 상승시키는 요인 중 하나.

케이스에 제시된 예제를 기준으로 구역을 사각형으로 도식화하면 아래와 같다.

위 사진과 같이 8x8 배열로 표현할 수 있다. 여기서 여기서 6번째 행까지 특수소대로 채울 수 있는 최소값은 어떻게 구할 수 있을까?

역으로 한번 생각해보자. 우리 특수소대는 너무나 유능해서 항상 최소의 팀만으로 목표 구역을 점령한다고 해보자. 작전 보고서엔 아래와 같이 점령한 구역을 표시하며, 이를 노란색 영역으로 마킹해서 보여준다.

즉, 노란색 영역은 최소의 특수소대팀이 투입된 것이며, 우리가 실제로 구현할 알고리즘의 결과물이기도 하다.

문제의 설정 상, 특수소대는 반드시 한 팀이 온전히 투입되어야 하며, 최소로 투입 가능한 인원 역시 한 팀이다. 그렇다면 위 사진에서 특수소대 한 팀이 커버할 수 있는 영역을 제외해보면 아래와 같이 세 케이스 $a$, $b$, $c$로 나눌 수 있다.

즉, 우리가 저 세 케이스에 대한 특수소대팀의 최소값을 계산할 수 있다면, 결과적으로 6번째 행 전체를 커버하는 특수소대팀의 수를 구할 수 있다. 이미 최소 인원이 나머지 구역을 점령한 상황에서, 투입할 수 있는 최소 인원인 한 팀만 투입할 수 있기 때문.

여러 블로그에서 위 세 그림을 많이 봤을 텐데, 뜬금없이 저런 그림이 등장함에는 이와같은 배경이 있는 것이다.

변수

---

알고리즘 설계에 사용할 변수는 아래와 같다.

• $T$: 케이스 수
• $N$: 구역의 행 수
• $e$: 구역별 적의 수
• $a_i$: 첫 번째 케이스의 특수소대 최소 투입 수
• $b_i$: 두 번째 케이스의 특수소대 최소 투입 수
• $c_i$: 세 번째 케이스의 특수소대 최소 투입 수

a 공식

---

첫번째 케이스로 $a_5$의 최소값 공식을 설계하자.

위에서 했던 방식과 마찬가지로 추론하면 $a_5$에서 한팀을 뺀 $a_5 - 1$을 구해야 하며, 이는 $e$의 조건에 따라 두 케이스로 나눌 수 있다.

일반적인 케이스

---

일반적으로 아래의 케이스가 해당된다.

$a_5 - 1 = c_5$ 이므로 $a_5 = c_5 + 1$

한팀이 두개의 구역을 커버할 수 있을 경우

---

$e_{04} + e_{05} ≤ W$일 경우에 한해 아래와 같은 케이스가 해당된다.

$a_5 - 1 = b_4$ 이므로 $a_5 = b_4 + 1$

일반적인 케이스와 비교했을 때, 더 작은 값이 $a_5$가 된다.

일반화

---

케이스별로 구한 식의 일반화는 아래와 같다.

• $a_5 = c_5 + 1$ -> $a_{i+1} = c_{i+1} + 1$
• $a_5 = b_4 + 1$ -> $a_{i+1} = b_i + 1$

즉, 최종 일반식은 아래와 같다.

b 공식

---

$b_5$의 최소값 공식을 설계하자.

$b_5$에서 한팀을 뺀 $b_5 - 1$을 구해야 하며, 이는 $e$의 조건에 따라 두 케이스로 나눌 수 있다.

일반적인 케이스

---

일반적으로 아래의 케이스가 해당된다.

$b_5 - 1 = c_5$ 이므로 $b_5 = c_5 + 1$

$a_5$의 식과 동일하다.

한팀이 두개의 구역을 커버할 수 있을 경우

---

$e_{14} + e_{15} ≤ W$일 경우에 한해 아래와 같은 케이스가 해당된다.

$b_5 - 1 = a_4$ 이므로 $b_5 = a_4 + 1$

일반적인 케이스와 비교했을 때, 더 작은 값이 $b_5$가 된다.

일반화

---

케이스별로 구한 식의 일반화는 아래와 같다.

• $b_5 = c_5 + 1$ -> $b_{n+1} = c_{n+1} + 1$
• $b_5 = a_4 + 1$ -> $b_{n+1} = a_n + 1$

즉, 최종 일반식은 아래와 같다.

c 공식

---

$c_5$의 최소값 공식을 설계하자. ($c_5$는 4행까지 채워짐에 유의하자)

$c_5$에서 한팀을 뺀 $c_5 - 1$을 구해야 하며, 이는 $e$의 조건에 따라 여러 케이스로 나눌 수 있다.

일반적인 케이스

---

일반적으로 아래의 케이스가 해당된다.

$c_5 - 1 = a_4$ 이므로 $c_5 = a_4 + 1$

$c_5 - 1 = b_4$ 이므로 $c_5 = b_4 + 1$

두 케이스 중 더 작은 케이스가 $c_5$이므로 아래의 식으로 귀결된다.

$c_5 = min(a_4 + 1, b_4 + 1)$

한팀이 두개의 구역을 커버할 수 있을 경우

---

$e_{04} + e_{14} ≤ W$일 경우 아래와 같은 케이스가 해당된다.

$c_5 = c_4 + 1$

일반적인 케이스와 비교했을 때, 더 작은 값이 $c_5$가 된다.

한팀이 네개의 구역을 커버할 수 있을 경우

---

$c_i$의 경우 한 가지 특이 케이스가 발생한다. $a_i$, $b_i$의 경우 최소 투입인원인 1을 뺀 값만을 계산했다. $c_i$의 경우 직사각형이라는 특징 때문에 최대 4개 구역을 2팀이 점령할 수 있다.

$e_{03} + e_{04} ≤ W$ 이고 $e_{13} + e_{14} ≤ W$일 경우 아래와 같은 케이스가 해당된다.

$c_5 = c_3 + 2$

모든 케이스와 비교했을 때, 더 작은 값이 $c_5$가 된다.

일반화

---

케이스별로 구한 식의 일반화는 아래와 같다.

• $c_{i+1} = min(a_{i} + 1, b_{i} + 1)$
• $c_{i+1} = c_{i} + 1$
• $c_{i+1} = c_{i-1} + 2$

즉, 최종 일반식은 아래와 같다.

최종 일반식

---

구한 일반식을 정리하면 아래와 같다.

원형 구조 적용을 위한 초기값 지정하기

---

위 수식을 코드로 녹여내면 되지만, 완벽한 건 아니다. 왜냐하면 이 구역이 선형이 아닌 원형 구조이기 때문.

지금까지 우리는 원리 이해 및 수식 도출의 편의를 위해 원타곤을 임의로 잘라 표타곤으로 전개하여 수식을 계산했다. 이러한 선형 구조는 시작점과 도착점이 있지만 원형은 순환 구조이므로 이에 맞춰 조건식을 작성해야 한다. 즉, 원형 구조에 호환되도록 일부 케이스에 초기값을 지정해야 최종적으로 원하는 알고리즘을 작성할 수 있다.

아래의 사진은 원타곤과 표타곤을 비교한 것이다.

이 처럼, 원형 구조는 $e_{00}, e_{07}$끼리도 연결이 가능하지만, 선형 구조는 구조상 불가능하다. 때문에 이러한 케이스들의 초기값을 지정해줘야한다.

대충 감이 오겠지만, 걸친 모양에 따라 총 4가지 케이스가 존재한다.

걸치지 않을 경우 (기본)

---

$e_{00}, e_{07}$ 혹은 $e_{10}, e_{17}$과 같이 영역이 겹치지 않을 경우. 선형 구조에서도 적용 가능한 기본적인 케이스다. $a_i, b_i, c_i$의 모양과 연관지어 생각하면 아래와 같이 도식이 가능하다.

$a_i$는 $i$열의 윗 칸만 채우므로 $e_{00}$만 점령한 상태이므로 1

$b_i$는 $i$열의 아래 칸만 채우므로 $e_{01}$만 점령한 상태이므로 1

$c_i$는 $i - 1$열을 채우는데, $c_{-1}$은 논리상 불가능하므로 0

즉 초기값은 아래와 같다.

$i = 0$일 때의 초기값을 지정한다.

이 케이스일 경우 $c_N$이 알고리즘의 답이 된다.

예를 들어, $N=8$일 경우 $c_8$이 되므로 가장 적합한 최소값을 구할 수 있다.

윗 행만 걸칠 경우

---

$e_{00}, e_{07}$을 점령할 경우. 원형 구조에서만 가능한 케이스다. 걸치지 않는 경우를 제외한 나머지 케이스는 전부 원형 구조에서만 가능한 케이스이니 참고할 것. $i = 0$일 때는 영향을 받지 않아 걸치지 않는 경우와 동일하다. 걸치기 위해선 반드시 두 행 이상이 필요하기 때문에, $N > 1$을 충족해야 한다.

연결된 부분을 체크패턴으로 하이라이팅 했다. 이 둘이 서로 연결되기 때문에, 다른 구역의 특수소대가 점령할 수 없다. 따라서 해당 부분은 초기값 계산 시 없는 영역으로 생각하면 된다. 이러한 특징을 감안하면 아래와 같이 초기값을 지정할 수 있다.

예제에서 $N = 8$이므로, 조건의 일반식은 $e_{00}, e_{0(N-1)}$이 된다.

$i = 1$일 때의 초기값을 추가로 지정한다.

이 케이스일 경우 $b_{N-1} + 1$이 알고리즘의 답이 된다. $e_{00}$, $e_{07}$을 합쳐 $e_{00}$이라고 생각하면 된다.

예를 들어, $N=8$일 경우 $b_7 + 1$이 되므로 가장 적합한 최소값을 구할 수 있다.

아래 행만 걸칠 경우

---

$e_{10}, e_{17}$을 점령할 경우. 세부 사항은 윗 행만 걸칠 경우와 동일하다.

예제에서 $N = 8$이므로, 조건의 일반식은 $e_{10}, e_{1(N-1)}$이 된다.

$i = 1$일 때의 초기값을 추가로 지정한다.

이 케이스일 경우 $a_{N-1} + 1$이 알고리즘의 답이 된다. $e_{10}$, $e_{17}$을 합쳐 $e_{10}$이라고 생각하면 된다.

예를 들어, $N=8$일 경우 $b_7 + 1$이 되므로 가장 적합한 최소값을 구할 수 있다.

두 행 모두 걸칠 경우

---

$e_{00}, e_{07}$, $e_{10}, e_{17}$을 점령할 경우. 세부 사항은 윗 행만 걸칠 경우와 동일하다.

예제에서 $N = 8$이므로, 조건의 일반식은 $e_{00}, e_{0(N-1)}$, $e_{10}, e_{1(N-1)}$이 된다.

$i = 1$일 때의 초기값을 추가로 지정한다.

이 케이스일 경우 $c_{N-1} + 2$이 알고리즘의 답이 된다. $e_{00}$, $e_{07}$을 합쳐 $e_{00}$, $e_{10}$, $e_{17}$을 합쳐 $e_{10}$이라고 생각하면 된다.

예를 들어, $N=8$일 경우 $c_{N-1} + 2$이 되므로 가장 적합한 최소값을 구할 수 있다.

최종 케이스

---

• 기본
  • $a_0 = 1$
  • $b_0 = 1$
  • $c_0 = 0$

• 윗 행만 걸칠 경우 $(e_{00} + e_{0(N-1))} ≤ W)$
  • $a_1 = 2$
  • $b_1 = \begin{cases} 1, & (e_{10} + e_{11} ≤ W)\\ 2, & (e_{10} + e_{11} > W) \end{cases}$
  • $c_1 = 1$

• 아래 행만 걸칠 경우 $(e_{10} + e_{1(N-1)} ≤ W)$
  • $a_1 = \begin{cases} 1, & (e_{00} + e_{01} ≤ W)\\ 2, & (e_{00} + e_{01} > W) \end{cases}$
  • $b_1 = 2$
  • $c_1 = 1$

• 두 행 모두 걸칠 경우 $(e_{00} + e_{0(N-1)} ≤ W)$, $(e_{10} + e_{1(N-1)} ≤ W)$
  • $a_1 = 1$
  • $b_1 = 1$
  • $c_1 = 0$

비로소 알고리즘을 구현하기 위한 모든 준비물이 갖춰졌다.

전체 소스

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 백준 전체 1006 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/06/a1006">1006 풀이</a>
 * @since 2021.06.06 Sun 22:44:45
 */
public class Main
{
	private static int N;
	private static int W;
	
	private static int[][] e;
	
	private static int[] a;
	private static int[] b;
	private static int[] c;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		// 케이스 수
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			int result = 2147483647;
			
			String[] temp = reader.readLine().split(" ");
			
			// 행 수
			N = Integer.parseInt(temp[0]);
			
			// 특수소대원 수
			W = Integer.parseInt(temp[1]);
			
			// 구역별 적 배열
			e = new int[2][N];
			
			for (int j = 0; j < 2; j++)
			{
				temp = reader.readLine().split(" ");
				
				for (int k = 0; k < N; k++)
				{
					e[j][k] = Integer.parseInt(temp[k]);
				}
			}
			
			a = new int[N];
			b = new int[N];
			c = new int[N + 1];
			
			a[0] = 1;
			b[0] = 1;
			c[0] = 0;
			
			// 인덱스 0부터 시작
			solve(0);
			
			result = Math.min(result, c[N]);
			
			// 두 행 이상일 경우
			if (N > 1)
			{
				// 두 행 모두 걸칠 경우
				if (e[0][0] + e[0][N - 1] <= W && e[1][0] + e[1][N - 1] <= W)
				{
					a[1] = 1;
					b[1] = 1;
					c[1] = 0;
					
					// 인덱스 1부터 시작 (1까지 초기값이 있기 때문)
					solve(1);
					
					result = Math.min(result, c[N - 1] + 2);
				}
				
				// 윗 행만 걸칠 경우
				if (e[0][0] + e[0][N - 1] <= W)
				{
					a[1] = 2;
					b[1] = e[1][0] + e[1][1] > W ? 2 : 1;
					c[1] = 1;
					
					// 인덱스 1부터 시작 (1까지 초기값이 있기 때문)
					solve(1);
					
					result = Math.min(result, b[N - 1] + 1);
				}
				
				// 아래 행만 걸칠 경우
				if (e[1][0] + e[1][N - 1] <= W)
				{
					a[1] = e[0][0] + e[0][1] > W ? 2 : 1;
					b[1] = 2;
					c[1] = 1;
					
					// 인덱스 1부터 시작 (1까지 초기값이 있기 때문)
					solve(1);
					
					result = Math.min(result, a[N - 1] + 1);
				}
			}
			
			System.out.println(result);
		}
		
		reader.close();
	}
	
	/**
	 * 알고리즘 함수
	 *
	 * @param num: [int] 시작 인덱스
	 */
	private static void solve(int num)
	{
		for (int i = num; i < N; i++)
		{
			c[i + 1] = Math.min(a[i] + 1, b[i] + 1);
			
			// c팀이 인접한 두 개의 구역을 점령할 수 있을 경우
			if (e[0][i] + e[1][i] <= W)
			{
				c[i + 1] = Math.min(c[i + 1], c[i] + 1);
			}
			
			// c팀이 인접한 두개의 구역 2개를 점령할 수 있을 경우
			if (i > 0 && e[0][i - 1] + e[0][i] <= W && e[1][i - 1] + e[1][i] <= W)
			{
				c[i + 1] = Math.min(c[i + 1], c[i - 1] + 2);
			}
			
			// a, b팀의 인덱스 보정 (c팀은 인덱스가 하나 더 많음)
			if (i < N - 1)
			{
				a[i + 1] = c[i + 1] + 1;
				b[i + 1] = c[i + 1] + 1;
				
				// a팀이 인접한 두 개의 구역을 점령할 수 있을 경우
				if (e[0][i] + e[0][i + 1] <= W)
				{
					a[i + 1] = Math.min(a[i + 1], b[i] + 1);
				}
				
				// b팀이 인접한 두 개의 구역을 점령할 수 있을 경우
				if (e[1][i] + e[1][i + 1] <= W)
				{
					b[i + 1] = Math.min(b[i + 1], a[i] + 1);
				}
			}
		}
	}
}

분류

---

• 다이나믹 프로그래밍

여담

---

6월 1일부터 풀기 시작해서 이 문제를 완전히 이해하는데 근 일주일 가까이 걸렸다. 나름의 풀이를 작성해야하는데, 남의 풀이가 아닌 내 풀이를 작성하기 위해선 해당 문제를 온전히 이해할 필요가 있었다. 내가 다른 사람들의 풀이를 보면서 이해하지 못해서 내 스스로 생각하고 이해한 걸 나름대로 녹여냈다. 다른 사람이 내 글을 보고 이 어려운 문제를 쉽게 이해할 수 있었으면 좋겠다.

이해하고 봐도 다소 난해한데, 이걸 원리부터 코드까지 이끌어내어 풀어내는 사람은 정말 대단한 거 같다. 아님 내가 실력이 없는건가.

참고

---

• 🔗 The Casterian
• 🔗 굳건하게
• 🔗 테스트 케이스