백준 1006 습격자 초라기

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

1006번: 습격자 초라기

 

풀이 

0. 문제를 풀기 앞서서 풀어야되는 문제

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

11726번: 2×n 타일링

피보나치 수열이라는 것을 알면 쉽게 풀리지만 왜 피보나치 수열로 되는지 생각하면서 풀어보는게 중요합니다.

 

 

1. 핵심 아이디어

해당 문제에서 주어지는 비밀국방기지(원타곤)은 원 모양으로 생겼습니다.

원모양으로 생겼기에 맨끝과 맨앞이 이어져있습니다. 이 부분을 고려해서 문제를 해결하는것은 조금 어렵기에

문제를 간략화하기 위해서는 원을 펼칠 필요가 있습니다.

 

특정 부분에 이미 특수부대를 배정했다고 전제하면 4가지 방법으로 펼쳐볼 수 있습니다.

첫번째. 맨끝부분과 맨앞부분을 동시에 커버하는 특수부대가 없는 경우

두번째. 맨끝부분과 맨앞부분을 동시에 커버하는 특수부대는 A만 있는 경우

세번째. 맨끝부분과 맨앞부분을 동시에 커버하는 특수부대는 B만 있는 경우

네번째. 맨끝부분과 맨앞부분을 동시에 커버하는 특수부대 A,B가 있는 경우

 

그리고 3가지 모양으로 현재상황이 표현할 수 있습니다.

첫번째. 특수부대가 다음 구역까지 검사 하지 않은 경우

두번째. 특수부대가 다음 구역까지 검사해서 A부분이 돌출된 경우

 

세번째. 특수부대가 다음 구역까지 검사해서 B부분이 돌출된 경우

 

 이를 토대로 간단하게 DP를 정의하면 다음과 같습니다.

DP[펼친모양(a)][현재상태(b)][현재 구역(i)] //펼친모양 a인 상태에서 현재 상태는 b이고 현재 i번 구역

​

위와 같은 그림처럼 다음 상태가 결정되고 이를 토대로 점화식을 만들 수 있습니다.

 단 주의해야하는 점은 펼친 모양에 따라서 끝부분과 시작부분의 점화식을 다르게 처리해야합니다.

(이미 할당된 부분과 겹칠 수 있다.)

 

자세한것은 코드를 참조해주세요.

코드

 

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const int INF = 999999999999999;
const int Dic[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

////////////////////////////////////////////////////////////////////////

int T;
int N, W;
//펼친상태,현재상태,현재위치
int DP[4][3][10001];
//원타곤
int A[2][10001];
vector<int> AnsList;
int Dp(int a, int b, int c)
{
	if (c == N)
		return 0;
	if (DP[a][b][c] != -1)
		return DP[a][b][c];
	int &ref = DP[a][b][c];
	ref = INF;
	//돌출되지 않은 경우 처리
	if (b == 0)
	{
		if (c == N - 1)
		{
			//끝부분일떼 처리
			if (a == 0)
			{
				if(A[0][c] + A[1][c] <= W)
					ref = min(ref, Dp(a, 0, c + 1) + 1);
				else
					ref = min(ref, Dp(a, 0, c + 1) + 2);
			}
			else if (a == 3)
			{
				ref = min(ref, Dp(a, 0, c + 1));
			}
			else 
			{
				ref = min(ref, Dp(a, 0, c + 1) + 1);
			}
		}
		else
		{
			if (A[0][c] + A[1][c] <= W)
			{
				ref = min(ref, Dp(a, 0, c + 1) + 1);
			}
			if (A[0][c] + A[0][c + 1] <= W)
			{
				if(c + 1 == N - 1 && a != 1 && a != 3)
					ref = min(ref, Dp(a, 1, c + 1) + 2);
				else if (c + 1 != N - 1)
					ref = min(ref, Dp(a, 1, c + 1) + 2);
			}
			if (A[1][c] + A[1][c + 1] <= W)
			{
				if (c + 1 == N - 1 && a != 2 && a != 3)
					ref = min(ref, Dp(a, 2, c + 1) + 2);
				else if (c + 1 != N - 1)
					ref = min(ref, Dp(a, 2, c + 1) + 2);
			}
			if (A[0][c] + A[0][c + 1] <= W && A[1][c] + A[1][c + 1] <= W)
			{
				if (a == 0 && c + 2 <= N)
					ref = min(ref, Dp(a, 0, c + 2) + 2);
				else if (a != 0 && c + 2 <= N - 1)
					ref = min(ref, Dp(a, 0, c + 2) + 2);
			}
			if(A[0][c] <= W && A[1][c] <= W)
				ref = min(ref, Dp(a, 0, c + 1) + 2);
		}
	}
	//A부분이 돌출된 경우
	else if (b == 1)
	{
		if (c == N - 1)
		{
			//끝부분일떼 처리
			if (a == 2)
			{
				ref = min(ref, Dp(a, 0, c + 1));
			}
			else
			{
				ref = min(ref, Dp(a, 0, c + 1) + 1);
			}
		}
		else
		{
			if (A[1][c] <= W)
			{
				ref = min(ref, Dp(a, 0, c + 1) + 1);
			}
			if (A[1][c] + A[1][c + 1] <= W)
			{
				if (c + 1 == N - 1 && a != 2 && a != 3)
					ref = min(ref, Dp(a, 2, c + 1) + 1);
				else if (c + 1 != N - 1)
					ref = min(ref, Dp(a, 2, c + 1) + 1);
			}
		}
	}
	//B부분이 돌출된 경우
	else if (b == 2)
	{
		if (c == N - 1)
		{
			//끝부분일떼 처리
			if (a == 1)
			{
				ref = min(ref, Dp(a, 0, c + 1));
			}
			else
			{
				ref = min(ref, Dp(a, 0, c + 1) + 1);
			}
		}
		else
		{
			if (A[0][c] <= W)
			{
				ref = min(ref, Dp(a, 0, c + 1) + 1);
			}
			if (A[0][c] + A[0][c + 1] <= W)
			{
				if (c + 1 == N - 1 && a != 1 && a != 3)
					ref = min(ref, Dp(a, 1, c + 1) + 1);
				else if (c + 1 != N - 1)
					ref = min(ref, Dp(a, 1, c + 1) + 1);
			}
		}
	}

	return ref;
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> T;
	while (T--)
	{
		memset(DP, -1, sizeof(DP));
		std::cin >> N >> W;
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < N; j++)
			{
				std::cin >> A[i][j];
			}
		}
		int ans = INF;
        //펼친 모양에 따른 정답 구하기
        
		ans = min(ans, Dp(0, 0, 0));
		if (A[0][0] + A[0][N - 1] <= W)
		{
			ans = min(ans, Dp(1, 1, 0) + 1);
		}
		if (A[1][0] + A[1][N - 1] <= W)
		{
			ans = min(ans, Dp(2, 2, 0) + 1);
		}
		if (A[0][0] + A[0][N - 1] <= W && A[1][0] + A[1][N - 1] <= W)
		{
			ans = min(ans, Dp(3, 0, 1) + 2);
		}
		AnsList.push_back(ans);
	}
    //정답출력
	for (int i = 0; i < AnsList.size(); i++)
		cout << AnsList[i] << endl;
}