백준 1006 습격자 초라기

이 문제는 풀이에 성공하지 못했으며 추후에 다시도전할 것이다. 내 성장과정을 기록하는 것이니.. 풀이에는 도움은 전혀 되지 않을 것이다.

초라기는 한국의 비밀국방기지(원타곤)를 습격하라는 임무를 받은 특급요원이다. 원타곤의 건물은 도넛 형태이며, 초라기는 효율적인 타격 포인트를 정하기 위해 구역을 아래와 같이 두 개의 원 모양으로 나누었다. (그림의 숫자는 각 구역의 번호이다.)

W명으로 구성된 특수부대 여럿을 각각 침투시켜 위 n*2개의 구역에 침투할 수 있다. 한부대마다 침투할 수 있는 구역은 2개씩이고 처음 침투된 구역의 인접한 구역에 한번 더 침투 가능하다(1의 인접구역은 2, 8, 9).

서로 다른 특수부대 끼리는 서로를 알아볼 수 없어 서로 공격이 발생하기 때문에 침투 구역이 겹칠 수 없다.

두구역을 침투하려고 할때 두지역의 적 수가 특수부대 수를 넘어서는 경우는 발생하면 안된다.

예제입력은 아래와 같고 답은 11이다.

1
8 100
70 60 55 43 57 60 44 50
58 40 47 90 45 52 80 40

 

이 문제을 어떻게 풀 것인가.. 고민을 하다가 두지역씩 합쳐서 특수부대수에 최대한 근접한 애들부터 하고
두지역으로 침투가 가능한 지점중 특수부대수에 근접한 순서부터 차례대로 침투하고 두지역으로 침투가 가능한 지점이 없어지면 한 지점씩 침투하여 몇부대가 투입되었는지 출력하도록 코드를 짰다.
 우선 스토리를 짜면서 작성한 코드는 아래와 같다.

#include <iostream>
#include <queue>
class area {
public:
	int enemies = 0;
};
class plan{
public:
	std::queue<int> twoAreas;
};
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	int t;
	std::cin >> t;
	while (t--) {
		int n, w;
		std::cin >> n >> w;
		area* areas = new area[n*2];
		plan* planLevel = new plan[w];
		for (int i = 0; i < n * 2; i++) {
			std::cin >> areas[i].enemies;
		}
		if (n > 1) {//좌우로 2개이상일때
			for (int i = 0; i < n * 2; i++) {//탐색
				if (i < n) {//안쪽 구역
					int next = i == n - 1 ? 0 : i + 1;
					int result = w - (areas[i].enemies + areas[next].enemies);
					if (result >= 0) {// 해당 두지역은 한부대로 감당 가능
						planLevel[result].twoAreas.push(i);
						planLevel[result].twoAreas.push(next);
					}
					next = i + n;
					result = w - (areas[i].enemies + areas[next].enemies);
					if (result >= 0) {// 해당 두지역은 한부대로 감당 가능
						planLevel[result].twoAreas.push(i);
						planLevel[result].twoAreas.push(next);
					}
				}
				else {//바깥 구역
					int next = i == n * 2 - 1 ? n : i + 1;
					int result = w - (areas[i].enemies + areas[next].enemies);
					if (result >= 0) {// 해당 두지역은 한부대로 감당 가능
						planLevel[result].twoAreas.push(i);
						planLevel[result].twoAreas.push(next);
					}
				}
			}
		}
		else {//좌우에 값이 없을때
			int result = w - (areas[n-1].enemies + areas[n * 2 - 1].enemies);
			if (result >= 0) {// 해당 두지역은 한부대로 감당 가능
				planLevel[result].twoAreas.push(n - 1);
				planLevel[result].twoAreas.push(n * 2 - 1);
			}
		}
		int troops = 0;
		for (int i = 0; i < w; i++) {//두지역침투작전. 레벨 0부터 순서대로 진행
			while (!planLevel[i].twoAreas.empty()) {
				int first = planLevel[i].twoAreas.front();
				planLevel[i].twoAreas.pop();
				int second = planLevel[i].twoAreas.front();
				planLevel[i].twoAreas.pop();
				if (areas[first].enemies == -1 || areas[second].enemies == -1) continue;
				troops++;//한부대 투입
				areas[first].enemies = -1;// 첫번째 구역 적 사살완료
				areas[second].enemies = -1;// 두번째 구역 적 사살완료
			}
		}
		for (int i = 0; i < n * 2; i++) {//남은 세력 파악후 한부대씩 투입하여 사살
			if (areas[i].enemies == -1) continue;
			troops++;//한부대 투입
			areas[i].enemies = -1;//적 사살 완료
		}
		//작전종료 투입된 부대수 출력
		std::cout << troops << "\n";
		delete[] areas, planLevel;
	}
	return 0;
}

스토리 순서로 재밌게 짜느라 효율은 생각하지 않았다. 

Test case 1

3
8 100
70 60 55 43 57 60 44 50
58 40 47 90 45 52 80 40

1 100
49
49

1 100
51
51

답
11
1
2

Test case 2
8
2 100
49 49
49 49

2 100
51 51
51 51

2 100
49 51
51 49

2 100
51 51
49 49

2 100
49 51
51 51

2 100
51 49
51 51

2 100
51 51
49 51

2 100
51 51
51 49

답
2
4
2
2
3
3
3
3

Test case 3
8
3 100
49 49 49
49 49 49

3 100
49 51 51
51 51 51

3 100
51 51 51
49 51 51

3 100
49 51 51
49 51 51

3 100
49 51 49
49 51 49

3 100
51 51 49
51 49 51

3 100
49 51 49
51 51 51

3 100
51 49 51
51 51 51

답
3
5
5
4
3
4
4
5

위 예제들을 모두 입력하여보았는데 결과가 잘 맞다.

해당 코드를 제출하여보자.

하... 진짜 한번만에좀 맞았으면 좋겠다. 질문게시판을 통해 반례를 찾아보았다.

1

7 100

7 9 84 70 5 32 11 

84 31 65 7 59 27 24

위 값을 내가 짠코드로 실행해보면 8이 나온다. 정답은 7이다.
내가 짠코드는 결과값이 큰 두 구역 위주로 짝을 지었기 때문에

7 84	9  84		70 7	5	32  11
	31  65			59  27		24

위와 같이 합쳐졌다. 정답은 어떻게 될까?

7 84	9  84		70 7	5  32		11 24
	31  65			59  27

이와 같이 7개의 부대면 충분히 소탕할 수 있는 적을 8개의 부대로 소탕했던 것이다.

위치 선정을 잘못하여 위와 같이 한 부대로 소탕 가능한 구역을 찢어놔서 두 개의 부대로 침투한 것이다.


내가 잘못생각했던 부분은 둘의 합이 최대한 큰쪽을 우선시하여 침투한다 였다. 둘의 합이 크건 작건 상관이 없었던 것이다. 최소한의 부대로 침투하기위해 어떻게 두지역을 최대한 많이 묶어서 침투하느냐가 핵심인 것이다.

내가 제시한 두개의 표와같이 모양이 어떻게 잡히고 그 모양이 다른선택에 어떻게 영향을 미치는가를 파악해야한다. 역시 쉽게 풀릴 문제가 아니었다...


포인트가 되는 구역에서 합이 W보다 낮은 지역이 몇개가 되는지 그 지역도 별개로 조건을 만족하는 지역이 몇개가 되는지 구하고 이 두 수를 합쳐 낮은쪽을 우선하도록 코드를 짜서 프로그램을 돌려보았다.
이역시 위의 예제들은 모두 통과하나, 제출시 틀렸다고 나온다..

#include <iostream>
#include <queue>
class area {
public:
	int enemies = 0;
	std::queue<int> aroundAreas;
};
class plan {
public:
	std::queue<int> twoAreas;
};
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	int t;
	std::cin >> t;
	while (t--) {
		int n, w;
		std::cin >> n >> w;
		area* areas = new area[n*2];
		plan* planLevel = new plan[6];
		for (int i = 0; i < n * 2; i++) {
			std::cin >> areas[i].enemies;
			if (n == 1) {//옆으로 구역이 하나밖에 없을때
				if (i == 0) continue;
				if (areas[n-1].enemies + areas[2 * n - 1].enemies <= w) {
					planLevel[0].twoAreas.push(n - 1);
					planLevel[0].twoAreas.push(2 * n - 1);
				}
			}
			else {
				if (i == 0) continue;
				if (i < n) {// 안쪽 구역
					int next = i - 1;
					if (areas[i].enemies + areas[next].enemies <= w) {
						areas[i].aroundAreas.push(next);
						areas[next].aroundAreas.push(i);
					}
					if(i == n - 1){
						next = 0;
						if (areas[i].enemies + areas[next].enemies <= w) {
							areas[i].aroundAreas.push(next);
							areas[next].aroundAreas.push(i);
						}
					}
				}
				else {// 바깥 구역
					int next = i - n;
					if (areas[i].enemies + areas[next].enemies <= w) {
						areas[i].aroundAreas.push(next);
						areas[next].aroundAreas.push(i);
					}
					if (i > n) {
						next = i - 1;
						if (areas[i].enemies + areas[next].enemies <= w) {
							areas[i].aroundAreas.push(next);
							areas[next].aroundAreas.push(i);
						}
					}
					if (i == n * 2 - 1) {
						next = n;
						if (areas[i].enemies + areas[next].enemies <= w) {
							areas[i].aroundAreas.push(next);
							areas[next].aroundAreas.push(i);
						}
					}
				}
			}
		}
		for (int i = 0; i < n * 2; i++) {
			if (areas[i].aroundAreas.empty()) continue;
			int size = areas[i].aroundAreas.size();
			while (areas[i].aroundAreas.size()) {
				int next = areas[i].aroundAreas.front();
				if (next == -1) break;
				areas[i].aroundAreas.pop();
				int level = size + areas[next].aroundAreas.size() - 2;
				planLevel[level].twoAreas.push(i);
				planLevel[level].twoAreas.push(next);
				areas[i].aroundAreas.push(-1);
			}
		}
		int troops = 0;
		for (int i = 0; i < 6; i++) {
			while (planLevel[i].twoAreas.size()) {
				int first = planLevel[i].twoAreas.front();
				planLevel[i].twoAreas.pop();
				int second = planLevel[i].twoAreas.front();
				planLevel[i].twoAreas.pop();
				if (areas[first].enemies == -1 || areas[second].enemies == -1) continue;
				troops++;
				areas[first].enemies = -1;
				areas[second].enemies = -1;
			}
		}
		for (int i = 0; i < n * 2; i++) {
			if (areas[i].enemies == -1) continue;
			troops++;
			areas[i].enemies = -1;
		}
		std::cout << troops << "\n";
		delete[] areas;
		delete[] planLevel;
	}
	return 0;
}

 

우선 순위를 매겨서 우선순위대로 찍는다고 무조건 최적의 결과가 나오는게 아니라고 생각은 하고있었다.
내가 작성한 위코드가 조금 높은 확률로 최적의 결과를 가져올 뿐인 것이다.

어떤 패턴이나 규칙을 찾아야만 하는 긴 싸움이 될 것 같다.. 이 문제 역시 내가 직접 풀고 싶어서 풀이를 보지 않고 풀고 있지만.. 부질없음이 느껴진다.

배우지 않고 도전하는건 원시인이 수학문제를 푸는 것과 같다.
수학의 공식들도 어찌보면 누군가가 굉장히 오랜시간 공들여서 발견한 공식이며 우리는 배움으로써 짧은시간을 투자하여 습득한다.

직접 풀어보는게 보람차며 다른 좋은 방법들을 볼때 이런게 있구나 하면서 더욱 감탄할 수 있다. 그리고 기억에도 오래 남는다. 그러나 배워야할건 많고 시간은 많지 않다. 1005번을 풀었을때 시간을 생각해보면... 자존심 상하지만 일단은 미련을 버리고 단계별 학습으로 뛰어드는게 더 현명하다 생각한다. 단계별로 넘어와 이문제를 다시 만났을때 그때 최선을 다하자.