[BOJ] 1006 : 습격자 초라기 - travelbeeee

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

---

[ 코멘트 ]

 처음에는 DP 말고 Set-cover Problem의 관점에서 습격자 초라기를 바라봤다.

 백준 예제 입력 1번을 가지고 다뤄보면,

  8 100

  70(1) 60(2)  55(3)   43(4)   57(5)  60(6)   44(7)   50(8)

  58(9) 40(10) 47(11) 90(12) 45(13) 52(14) 80(15) 40(16)

  총 16개의 구역이 존재하고, 한 소대가 최대 100명을 처리할 수 있다.

 이때, 한 번에 두 구역을 커버 가능한 경우를 모두 뽑아보면 다음과 같다.

 { 2, 10 }, { 3, 4 }, { 4, 5 }, { 7, 8 }, { 8, 16 }, { 9, 10 }, { 10, 11 }, { 13, 14 }, { 9, 16 } 이고

 여기에서 선택받지 못한 { 1 }, { 6 }, { 12 }, { 15 } 는 무조건 하나의 특수 소대가 커버해야 한다.

 따라서 이 문제를 집합 U = { 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 16 } 를

 S = { { 2, 10 }, { 3, 4 }, { 4, 5 }, { 7, 8 }, { 8, 16 }, { 9, 10 }, { 10, 11 }, { 13, 14 }, { 9, 16 } } 에서

 최소 개수의 원소들을 뽑아서 집합 U를 만드는 문제로 바라보려 했다.

 하지만, 이런 Set-cover Problem은 NP hard Problem으로 항상 최적의 해를 구하는 알고리즘이 없어서,,, 포기했다,,,,

 그 후, DP 배열을 아무리 생각해도 아이디어가 떠오르지 않아 DP 배열 정의만 포스팅을 참고해 문제를 풀고 다른 분들 코드랑 비교해보는 시간을 가졌다...! ( 언제쯤 혼자서 이 정도 문제를 풀 수 있을까... )

 

[ 알고리즘풀이 ]

정의 )

 Enemy[2][N] := Enemy[0][N] 은 바깥쪽 구역, Enemy[1][N] 은 안쪽 구역의 적의 수입니다.

 DP[0][N] := 바깥쪽구역 1 ~ N, 안쪽구역 1 ~ N - 1 을 커버하는데 필요한 최소 특수 부대의 수.

 DP[1][N] := 바깥쪽구역 1 ~ N - 1, 안쪽구역 1 ~ N 을 커버하는데 필요한 최소 특수 부대의 수.

 DP[2][N] := 바깥쪽구역 1 ~ N, 안쪽구역 1 ~ N 을 커버하는데 필요한 최소 특수 부대의 수.

DP[0][5] 예시

DP[1][5] 예시

DP[2][5] 예시

점화식 )

 DP[0][N] =  min(dp[1][N - 1] + outer, dp[2][N - 1] + 1, );

 DP[1][N] = min(dp[0][N - 1] + inner, dp[2][N - 1] + 1, );
 DP[2][N] = min({ dp[0][N] + 1, dp[1][N] + 1, dp[2][N - 1] + horizon, , dp[2][N - 2] + outer + inner });

 

 그림으로 위의 점화식을 자세히 이해해보겠습니다.

1) DP[0][N]

DP[0][5] 는 아래와 같은 2가지 경우 중에 하나로 값을 찾을 수 있습니다.

 DP[1][4] 에서 Out4랑 Out5를 커버하는데 필요한 특수 소대의 수(Outer) 를 더한 값이랑,

 DP[2][4] 에서 Out5를 커버하는 특수 소대의 수(1) 을 더한 값 중 작은 값이 됩니다.

 즉, 다음과 같은 점화식을 얻을 수 있습니다.

 DP[0][N] =  min(dp[1][N - 1] + outer, dp[2][N - 1] + 1, );

 

2) DP[1][N]

 DP[1][5] 은 아래와 같은 2가지 경우 중에 하나로 값을 찾을 수 있습니다.

 즉, 다음과 같은 점화식을 얻을 수 있습니다.

 DP[1][N] = min(dp[0][N - 1] + inner, dp[2][N - 1] + 1, ); 

 

3) DP[2][N]

 DP[2][5] 는 아래와 같은 4가지 경우 중에 하나로 답을 찾을 수 있습니다.

 위에서 DP[0][5], DP[1][5] 의 값을 먼저 구했으므로, 그 값들을 이용해서 DP[2][5] 를 채울 수 있습니다.

 따라서, 다음과 같은 점화식이 성립합니다.

 DP[2][N] = min({ dp[0][N] + 1, dp[1][N] + 1, dp[2][N - 1] + horizon, , dp[2][N - 2] + outer + inner });

 

 하지만, 이렇게 DP 배열을 채워나가면 원형으로 이어져있다는 점을 고려하지 못하기 때문에, Out[1] 과 Out[N]을 동시에 커버할 수 있는 경우, In[1]과 In[N]을 동시에 커버할 수 있는 경우, Out[1] 과 Out[N] / In[1]과 In[N]을 동시에 커버할 수 있는 경우에 대해서도 초기값을 다르게 해서 DP 배열을 채우고 총 4가지 경우에 대해서 가장 작은 값을 답으로 출력하면 됩니다.

#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 987654321

using namespace std;

int dp[3][10001], N, W, enemy[2][10001];

void solve(void) { // 그냥 점화식대로 DP배열을 채우는 함수.
	for (int i = 2; i <= N; i++) {
		int outer = 2 - (enemy[0][i] + enemy[0][i - 1] <= W);
		int inner = 2 - (enemy[1][i] + enemy[1][i - 1] <= W);
		int horizon = 2 - (enemy[0][i] + enemy[1][i] <= W);

		dp[0][i] = min(dp[2][i - 1] + 1, dp[1][i - 1] + outer);
		dp[1][i] = min(dp[2][i - 1] + 1, dp[0][i - 1] + inner);
		dp[2][i] = min({ dp[2][i - 1] + horizon, dp[0][i] + 1, dp[1][i] + 1, dp[2][i - 2] + outer + inner });
	}
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int T;
	cin >> T;
	while (T--) {
		cin >> N >> W;
		for (int i = 0; i < 2; i++)
			for (int j = 1; j <= N; j++)
				cin >> enemy[i][j];

		if (N == 1) {
			cout << 2 - (enemy[0][1] + enemy[1][1] <= W) << '\n';
			continue;
		}

		int ans = INF;
		memset(dp, 0, sizeof(dp));

		dp[0][1] = dp[1][1] = 1; 
		dp[2][1] = 2 - (enemy[0][1] + enemy[1][1] <= W);
		solve();

		ans = min(ans, dp[2][N]);
		if (enemy[0][N] + enemy[0][1] <= W) {
			dp[2][0] = INF; dp[0][1] = 1; dp[1][1] = INF; dp[2][1] = 2;
			solve();
			ans = min(ans, dp[1][N]);
		}

		if (enemy[1][N] + enemy[1][1] <= W) {
			dp[2][0] = INF; dp[1][1] = 1; dp[0][1] = INF; dp[2][1] = 2;
			solve();
			ans = min(ans, dp[0][N]);
		}

		if (enemy[0][N] + enemy[0][1] <= W && enemy[1][N] + enemy[1][1] <= W) {
			dp[2][0] = INF; dp[0][1] = dp[1][1] = INF; dp[2][1] = 2;
			solve();
			ans = min(ans, dp[2][N - 1]);
		}

		cout << ans << '\n';
	}
}

---