BOJ 1006 습격자 초라기

https://www.acmicpc.net/problem/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)

풀이

2*n타일링처럼 풀면 된다. 단, 1칸짜리 블럭을 사용한다는 점과 원형이라는 점을 생각해 줘야 한다. 

 

길이가 2인 방향을 세로, n인 방향을 가로라고 하자.

블럭을 어떻게 쌓을 수 있을까를 생각해 보자. 가로방향으로 이동하면서 DP배열을 채워나간다.

바깥에 있는 구역은 어떤 구역과도 연결되어있지 않거나 안쪽 구역과 연결되어있거나 왼쪽 구역과 연결되어있거나 오른쪽 구역과 연결되어있을 수 있다. 반대로, 어떤 구역과도 연결되어있지 않거나 안쪽에 있는 구역은 바깥쪽 구역과 연결되어있거나 왼쪽 구역과 연결되어있거나 오른쪽 구역과 연결되어있을 수 있다. 안쪽 구역이 바깥쪽 구역과 연결되어있다면 같은 세로줄의 바깥쪽 구역은 안쪽 구역과 연결되어있어야 하므로 한 개의 세로줄이 가질 수 있는 연결의 방법은 총 10가지이다.

10가지 경우에 대해 다음 DP배열을 채울 때 가능한 연결 방법이 있고 불가능한 방법이 있다. 따라서 가능한 모든 방법을 토대로 DP 배열을 채우면 된다.

마지막으로 모든 배열을 다 채웠다면 첫 번째 세로줄과 마지막 세로줄을 비교하면서 가능한 모든 연결방식의 DP 배열의 값을 더해주면 된다. 

 

실제로 10가지 모든 경우의 수를 하드코딩해서 해결했다. 

먼저 각 세로줄이 왼쪽과 연결되어있는지, 오른쪽과 연결되어있는지를 크기 10인 배열로 미리 저장해둔다. 바깥쪽이 왼쪽과 연결되어있다면 2, 안쪽이 왼쪽과 연결되어있다면 1, 둘 다 연결되어있다면 3, 둘 다 연결되어있지 않다면 0으로 두고 해결했다. 오른쪽도 마찬가지로 미리 저장해서 해결했다. 

k번째 경우의 수의 왼쪽 모양을 left[k], 오른쪽 모양을 right[k]라고 두면 아래와 같이 미리 모양을 만들어둘 수 있다.

	0	1	2	3	4	5	6	7	8	9
left	0	0	0	1	0	0	1	2	2	3
right	0	0	1	0	2	3	2	0	1	0

왼쪽의 경우와 오른쪽의 경우를 분리한 이유는 i번째 세로줄과 i+1번째 세로줄이 연결될 수 있는지 확인하기 위해 right[i]==left[i+1]을 바로 이용하기 위해서이다. 0번과 1번의 경우 left와 right가 동일한데, 이를 구분해 줄 방법이 필요하다.

어떤 칸이 왼쪽 또는 오른쪽과 연결되어있는 경우 이를 0.5개의 소대를 사용한다고 생각해도 동일한 답을 얻을 수 있다.

이때 각 세로줄이 연결상태에 따라 사용할 소대의 수를 미리 계산해서 넣어두자. 

	0	1	2	3	4	5	6	7	8	9
size	1	2	1.5	1.5	1.5	1	1	1.5	1	1

소수를 저장하게 되는 것은 마음에 들지 않는다. 두 배 해서 저장해 두고 마지막 최종 답을 구할 때 2로 나누자. 두 배 한 뒤의 최종 답이 홀수가 나오는 경우는 없다.

	0	1	2	3	4	5	6	7	8	9
newsize	2	4	3	3	3	2	2	3	2	2

다음으로 DP배열을 구성하자. 

DP[x][type]=> 마지막이 type으로 끝나면서 x번째 세로줄까지의 최적해라 두면, 

DP[x][type]는 left[type]와 right[pretype]의 값을 같게 만들면서 연결되어  있는 소대의 총원이 W보다 작게 되는 모든 pretype에 대해 DP[x-1][pretype]의 합과 같다.

이런식으로 DP배열을 모두 채운다. 

단, 마지막 세로줄의 경우 DP배열을 채울 때 한가지 더 고려해 줘야할 대상이 있다. 바로 첫 번째 세로줄과 연결할 수 있는지 여부이다. right[x]에 따라 첫 번째 세로줄과 연결했을 때 소대의 총원이 W보다 큰 경우가 있다면 최적해 계산에서 제외해 줘야 한다. 

 

마지막으로, 이렇게 채워진 DP[N-1] 배열의 최소값을 찾아 "2로 나눈" 값이 정답이 된다.