백준 2647: 검은점과 하얀점의 연결

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

 

이 문제는 예전에 해결했던 문제지만, 정말 사소한 실수로 약 4달간 고민을 했고, 겨우 푼 문제이다.

사실 이 문제는

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

"백준 2673: 교차하지 않는 원의 현들의 최대집합"의 상위호환 문제다.

한계치를 DP의 파라미터로 둔다는 점에서, 위의 문제와 비슷하다. 하지만, 이 문제가 더 어려운 점은 누적합 개념이 들어가고 역추적도 해야한다. 그렇기 때문에 더 풀기 힘들다.

 

일단 DP는 다음과 같이 구하면 된다.

DP[현재 위치][현재 위치 한계치][현재 높이 한계치]

이 식의 다음 식은

min(DP[현재 위치 + 1][매칭 위치 - 1][임의의 높이 한계치] + DP[매칭 위치][현재 한계치][현재 높이 한계치] + 선분 길이)

 

매칭 위치는 for문을 돌며 현재 위치와 동일한 점이고, 현재위치와 매칭 위치 사이의 검은점과 하얀점 갯수가 같은 위치를 선정하면 된다. 이를 위해 누적합을 활용한다. 임의의 높이 또한 for문을 돌며 현재 높이 이하의 높이로 선정한다. C++의 코드로 나타내면 다음과 같다.

int solve(int here, int e, int height)
{
	int& ret = dp[here][e][height];
	if (ret != -1) return ret;
	ret = INF;
	if (here > e) return ret = 0;
	for (int there = here + 1; there <= e; there++)
		if (str[here] != str[there] && black[there] - black[here - 1] == white[there] - white[here - 1])
			for (int h = 1; h < height; h++)
				ret = min(ret, solve(here + 1, there - 1, h) + solve(there + 1, e, height) + (there - here + (2 * h)));
	return ret;
}

역추적도 동일한 원리로 구하면 끝이다.

void reconstruct(int here, int e, int height)
{
	if (here > e) return;
	for (int there = here + 1; there <= e; there++)
	{
		if (str[here] != str[there] && black[there] - black[here - 1] == white[there] - white[here - 1])
			for (int h = 1; h < height; h++)
			{
				if (dp[here + 1][there - 1][h] < 0 || dp[there + 1][e][height] < 0) continue;
				if (dp[here][e][height] == dp[here + 1][there - 1][h] + dp[there + 1][e][height] + (there - here + (2 * h)))
				{
					order.push_back({ here, there });
					reconstruct(here + 1, there - 1, h);
					reconstruct(there + 1, e, height);
				}
			}
	}
}

 

여기까지 아이디어는 문제가 없었다. 그렇기 때문에 나는 내가 맞을 것이라 생각했다. 그런데 틀렸다. 그 후로 여러 시도를 했지만, 결국 문제를 해결한 것은 3~4개월 뒤였다.

어느날 이 문제에 다시 도전하려고, 예시를 만들어서 디버깅을 하던 중에, 너무나 사소한 실수를 했다는 것을 깨달았다.

이 문제는 스페셜 저지 문제이다. 즉, 답은 여러 개일 수도 있고, 답은 하나만 제시해야한다. 그런데, 내 코드는 복수 정답을 한번에 출력하고 있다. 즉, 역추적 뒤에 바로 Break하지 않아서 문제가 된것이다.

void reconstruct(int here, int e, int height)
{
	if (here > e) return;
	bool br = false;
	for (int there = here + 1; there <= e; there++)
	{
		if (br) break;
		if (str[here] != str[there] && black[there] - black[here - 1] == white[there] - white[here - 1])
			for (int h = 1; h < height; h++)
			{
				if (dp[here + 1][there - 1][h] < 0 || dp[there + 1][e][height] < 0) continue;
				if (dp[here][e][height] == dp[here + 1][there - 1][h] + dp[there + 1][e][height] + (there - here + (2 * h)))
				{
					order.push_back({ here, there });
					reconstruct(here + 1, there - 1, h);
					reconstruct(there + 1, e, height);
					br = true;
					break; // BREAK!
				}
			}
	}
}

지금 생각해도 너무 어이가 없는 실수다. 겨우 이것 때문에 고민한 내가 바보같다..

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

const int INF = 100000000;
int N, dp[105][105][105];
string str;
int black[105], white[105];
vector<pair<int, int>> order;
int solve(int here, int e, int height)
{
	int& ret = dp[here][e][height];
	if (ret != -1) return ret;
	ret = INF;
	if (here > e) return ret = 0;
	for (int there = here + 1; there <= e; there++)
		if (str[here] != str[there] && black[there] - black[here - 1] == white[there] - white[here - 1])
			for (int h = 1; h < height; h++)
				ret = min(ret, solve(here + 1, there - 1, h) + solve(there + 1, e, height) + (there - here + (2 * h)));
	return ret;
}

void reconstruct(int here, int e, int height)
{
	if (here > e) return;
	bool br = false;
	for (int there = here + 1; there <= e; there++)
	{
		if (br) break;
		if (str[here] != str[there] && black[there] - black[here - 1] == white[there] - white[here - 1])
			for (int h = 1; h < height; h++)
			{
				if (dp[here + 1][there - 1][h] < 0 || dp[there + 1][e][height] < 0) continue;
				if (dp[here][e][height] == dp[here + 1][there - 1][h] + dp[there + 1][e][height] + (there - here + (2 * h)))
				{
					order.push_back({ here, there });
					reconstruct(here + 1, there - 1, h);
					reconstruct(there + 1, e, height);
					br = true;
					break;
				}
			}
	}
}
int main()
{
	memset(dp, -1, sizeof(dp));
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> N;
	cin >> str;
	str = 'S' + str;
	black[0] = 0; white[0] = 0;
	for (int i = 1; i <= N; i++)
	{
		black[i] = black[i - 1] + (str[i] == '1');
		white[i] = white[i - 1] + (str[i] == '0');
	}
	cout << solve(1, N, (N / 2) + 1) << '\n';
	reconstruct(1, N, (N / 2) + 1);
	sort(order.begin(), order.end());
	for (int i = 0; i < order.size(); i++)
		cout << order[i].first << " " << order[i].second << '\n';
}