백준 1006번 습격자 초라기 문제 풀이

https://www.acmicpc.net/problem/1006

1006번: 습격자 초라기

 

백준저지 1006번 문제 습격자 초라기 문제입니다. 악명높은 문제이죠?

1000번 부터 하나씩 문제를 풀려고 하는 PS 입문자를 접게 만드는 문제입니다.

 

다이나믹 프로그래밍으로 풀 수 있는 문제이며, 2xn 타일링, 스티커 문제와 유사한 점이 좀 있습니다.

 

점령해야 하는 공간이 2줄로 이루어져 있고, 최대 2개의 인접한 공간을 같이 점령할 수 있다는 점에 있어서 그렇죠

 

2x1짜리 블럭을 가로, 세로로 놓아서 2줄자리 칸을 채우는 2xn 타일링 문제 (https://www.acmicpc.net/problem/11726)

 

2줄짜리 스티커를 때되, 땔때마다 인접한 스티커는 못쓰게 되는 스티커 문제 (https://www.acmicpc.net/problem/9465)

와 유사합니다.

 

다만 조금 번거로운 부분은, 공간이 환형(동그란 형태)이므로 처음과 끝을 연결시켜줘야 한다는 점입니다.

 

처음과 끝부분이 가로로 겹치게 되면 조금 골치 아파 지죠.

 

그래서 경우를 4가지로 나누어서 각각 처리해줘야 합니다.

 

1) 처음과 끝에 걸치는 경우가 없는 경우

2) 위만 걸치는 경우

3) 아래만 걸치는 경우

4) 위아래 둘다 걸치는 경우

 

각각 걸치는 경우가 성립할 때, 걸치는 부분의 적 병력 수를 W로 바꾼 뒤 문제를 풀면, 다른 곳과는 겹쳐서 점령될 일은 없습니다.

걸치는 부분의 병력 수를 W로 바꾸어서 문제를 푼 뒤, 마지막 부분의 걸치는 부분은 점령하지 않았을 때의 dp 배열을 리턴하면 정답과 같습니다.

 

dp배열 정의는 다음과 같습니다.

 

a[x] => 0~x-1 열까지 모두 점령하고, x번째 열은 위 아래 둘다 점령한 경우

b[x] => 0~x-1 열까지 모두 점령하고, x번째 열은 위 만 점령한 경우

c[x] => 0~x-1 열까지 모두 점령하고, x번째 열은 아래 만 점령한 경우

 

개인적으로 문제 푸는데 코너케이스를 잘 찾지 못해서 매우 고생한 문제입니다.

다음 블로그의 풀이 코드를 조금 참고 했습니다(https://casterian.net/archives/1356)

 

해당 블로그에서는 "a[x] => x-1열까지만 위 아래 모두 점령한 경우" 로 정의하여 b, c DP 배열에 비해서 한칸 뒤까지만 점령한 것으로 정의를 하였는데

 

코너 케이스를 찾다 보니 왜 그렇게 했는지 약간 이해가 갔습니다.

 

제 코드를 보시면, 가로로 두개를 놓는 경우 i == 1인 경우 따로 예외 처리를 해 주었는데, 위 casterian 블로그 주인분이 작성한 코드식으로 정의를 하면 해당 부분을 따로 처리할 필요가 없어집니다.

 

해당 코너 케이스를 찾기 위해서 종만북에서 말하는 스캐폴딩 방법을 활용했습니다.

 

다른곳에서 사용하는 스캐폴딩이라는 단어 뜻은 조금 상이할 수 있으므로 좀더 첨언을 하자면,

랜덤하게 input 값을 생성해서, 정답 소스로 작성한 바이너리와 제가 작성한 오답 바이너리에 각각 input 값을 집어 넣고

output 값을 비교합니다. 

 

다른 output 값이 나올 때 까지 계속 반복하고, 다른 output을 만들어내는 input 파일을 토대로 디버깅을 해서 코너 케이스를 찾아내었습니다.

 

자세한 내용은 코드와 주석들을 확인해주시기 바랍니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int N, W;
int cost[2][10004];
int a[10004], b[10004], c[10004];
void expand() {
	if (cost[0][0] + cost[1][0] <= W) {
		a[0] = b[0] = c[0] = 1;
	}
	else {
		a[0] = 2;
		b[0] = c[0] = 1;
	}
	for (int i = 1; i < N; i++) {
		// i번째 칸에 놓는 방법을 해결한다.
		// i-1까지의 값은 최신임을 보장한다.

		//기존 열에서 두개 그대로 놓는 경우
		a[i] = a[i - 1] + 2;

		//하나만 달랑 놓는 경우
		b[i] = c[i] = a[i - 1] + 1;

		//위로 가로 하나 놓는 경우
		if (cost[0][i] + cost[0][i - 1] <= W) {
			b[i] = min(b[i], c[i - 1] + 1);
		}

		//아래로 가로 하나 놓는 경우
		if (cost[1][i] + cost[1][i - 1] <= W) {
			c[i] = min(c[i], b[i - 1] + 1);
		}

		//하나만 달랑 다시 놓는 경우
		a[i] = min(a[i], b[i] + 1);
		a[i] = min(a[i], c[i] + 1);
		
		//세로로 놓는 경우
		if (cost[0][i] + cost[1][i] <= W) {
			a[i] = min(a[i], a[i - 1] + 1);
		}
		//가로로 두개 놓는 경우
		if (cost[0][i] + cost[0][i - 1] <= W && cost[1][i] + cost[1][i - 1] <= W) {
			if (i >= 2)
				a[i] = min(a[i], a[i - 2] + 2);
			else
				a[i] = min(a[i], 2);
		}
	}

}
void solve() {
	cin >> N >> W;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < N; j++) {
			cin >> cost[i][j];
		}
	}
	int ans;

	expand();
	//cout << "교차 없는 경우 : ";
	ans = a[N - 1];
	//cout << a[N - 1] << endl;

	if (N > 1) {
		//아래쪽 라인 교차 있는 경우
		if (cost[1][0] + cost[1][N - 1] <= W) { 
			int tmp1 = cost[1][0];
			int tmp2 = cost[1][N - 1];
			cost[1][0] = cost[1][N - 1] = W;
			expand();
			//cout << "아래 교차있는 경우 : ";
			//cout << b[N - 1] << endl;
			ans = min(ans, b[N - 1]);
			cost[1][0] = tmp1;
			cost[1][N - 1] = tmp2;
		}
		if (cost[0][0] + cost[0][N - 1] <= W) {
			int tmp1 = cost[0][0];
			int tmp2 = cost[0][N - 1];
			cost[0][0] = cost[0][N - 1] = W;
			expand();
			//cout << "위 교차 있는 경우 : ";
			//cout << a[N - 1] << endl;
			ans = min(ans, c[N - 1]);
			cost[0][0] = tmp1;
			cost[0][N - 1] = tmp2;
		}
		if (cost[0][0] + cost[0][N - 1] <= W && cost[1][0] + cost[1][N - 1] <= W) {
			int tmp1 = cost[0][0];
			int tmp2 = cost[0][N - 1];
			int tmp3 = cost[1][0];
			int tmp4 = cost[1][N - 1];
			cost[1][0] = cost[1][N - 1] = W;
			cost[0][0] = cost[0][N - 1] = W;
			expand();
			//cout << "위 아래 둘다 교차 있는 경우 : ";
			//cout << a[N - 2] << endl;
			ans = min(ans, a[N - 2]);
			cost[0][0] = tmp1;
			cost[0][N - 1] = tmp2;
			cost[1][0] = tmp3;
			cost[1][N - 1] = tmp4;

		}
	}
	cout << ans << endl;

}
int main() {
	int tc; cin >> tc;
	while (tc--) {
		solve();
	}
}