[백준] 1006번 습격자 초라기

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

 

 

1. Approach

 

(1) 다이나믹 프로그래밍으로 접근한다.

 

-> 영역별로 묶을 수 있는 (최대 2개) 영역들을 표시해나가면서 경우에 따라 재귀함수를 호출하면서 메모이제이션 한다.

 

영역의 상태는 아래와 같이 가정하였고 prev, last가 이 상태를 나타낸다.

 

0 -> not used

1 -> inner used

2 -> outer used

3 -> both used

 

위 상태를 정의하면서 상황에 맞게 따라나가면서 문제를 풀어나가는 방식이다.

 

(2) DP 배열 정의

 

-> DP[idx][prev][last] : idx까지 이전 블록의 상태가 prev 이고 마지막 블록 n - 1 상태가 last 일 때 까지의 최소 초라기 수

 

(3) 후기

 

조건, 경우의 수가 까다롭고 많다 보니까 쉽게 풀리지 않는 문제였다.

아래 링크 블로그에서 코드를 읽어가기에도 깔끔하게 알고리즘을 풀어주셨다. 

( 삼항연산자로 코드르 이렇게 이쁘게 만들 수 있다는 점을 깨닫기도 했다. )

 

참고 : blog.naver.com/whgksdyd112/220956454574

2. Source Code

 

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int map[10000][2];
int dp[10000][4][4];
int n, w;
/*
	0 -> not used, 
	1 -> inner used, 
	2 -> outer used, 
	3 -> both used
*/

int solution(int index, int prev, int last)
{
	int& result = dp[index][prev][last];
	if (result) return result;
	bool inner, outer, both;
	// 이전 블록 (index - 1)과 묶을 수 있는지 판별
	inner = (map[index][0] + map[index ? index - 1 : n - 1][0] <= w);
	outer = (map[index][1] + map[index ? index - 1 : n - 1][1] <= w);
	// 안밖이 묶일 수 있는지 확인
	both = (map[index][0] + map[index][1] <= w);
	// index가 끝에 도달했을 때
	if (index == n - 1) {
		if (index == 0) return both ? 1 : 2;

		// 최소 2개의 팀이 필요하다.
		result = 2;
		if (last == 0) {
			if (inner && !(prev & 1)) result = 1;
			if (outer && prev < 2) result = 1;
			if (both) result = 1;
			if (inner && outer && prev == 0) result = 0;
		}
		else if (last == 1) {
			if (outer && prev < 2) result = 1;
		}
		else if (last == 2) {
			if (inner && !(prev & 1)) result = 1;
		}
		return result;
	}
	// 구역을 묶지 않을 때 ( 최소 2개의 팀 필요 )
	result = 2 + solution(index + 1, 0, index ? last : 0);
	// 안쪽 구역을 묶을 때
	if (inner && !(prev & 1)) result = min(result, 1 + solution(index + 1, 1, index ? last : 1));
	// 바깥 구역을 묶을 때
	if (outer && prev < 2) result = min(result, 1 + solution(index + 1, 2, index ? last : 2));
	// 안쪽과 바깥 구역을 각각 묶을 때 , 팀이 더 필요하지 않다.
	if (inner && outer && prev == 0) result = min(result, solution(index + 1, 3, index ? last : 3));
	// 안쪽과 바깥 구역을 함께 묶을 때
	if (both) result = min(result, 1 + solution(index + 1, 3, index ? last : 0));
	return result;
}
int main()
{
	int c; scanf("%d", &c);
	while (c--) {

		memset(map, 0, sizeof(map));
		memset(dp, 0, sizeof(dp));
		scanf("%d%d", &n, &w);
		for (int i = 0; i < n; i++) scanf("%d", &map[i][0]);
		for (int i = 0; i < n; i++) scanf("%d", &map[i][1]);
		printf("%d\n", solution(0, 0, 0));
	}
}