[C++] 백준 5577번: RBY팡!

문제 링크

5577번: RBY팡!

문제 요약

3가지 색을 가진 공들이 주어진다. 같은 색의 공 4개가 연속해서 있다면 그 공들은 폭발하게 된다. N개의 공 중에서 하나의 색깔을 바꿨을 때 연쇄적으로 폭발이 일어날 수 있다. 이때 남을 수 있는 공의 갯수의 최솟값을 구해야 한다.

접근 방법

기본적인 접근 방법은 브루트포스 알고리즘이 맞지만 10000개에 대해서 전부 바꿔볼 이유는 없을 것이라고 생각했습니다. 만약 3개 이상의 연속된 공에 대해서 그 사이에 있는 공의 색깔을 바꾸면 공은 터지지 않습니다. 즉, 연속된 색깔을 가진 공들의 그룹에서는 양 끝의 공만 색을 바꿔보면 됩니다. 따라서, 연속된 같은 색깔의 공들은 그냥 pair 묶어서 색깔과, 사이즈를 함께 저장했습니다.

이제 모든 공 그룹에 대해서 그 그룹의 양 끝단의 공 색깔을 인접한 그룹의 색깔로 바꿔서 검사해보면 됩니다. 방법은, 현재 그룹의 크기를 1 감소시키고, 그 인접한 그룹의 크기를 1 증가시킵니다. 인접한 그룹은 2개이기 때문에, 2번 해봐야 합니다. 이때 인접한 그룹의 크기를 증가시켰을 때, 크기가 4가 된다면 재귀호출을 통해서 그 그룹과 인접한 두 그룹을 비교합니다. 만약 이 두 그룹의 색깔이 같고, 크기의 합이 4 이상이라면 재귀호출을 통해서 재차 검사해줍니다. 이런식으로 최소값을 계산해준 뒤에, 크기가 변경되었던 그룹들의 크기를 다시 원래대로 돌려주면 됩니다.

그룹의 크기가 1인 경우에는 추가적인 검사가 필요합니다. 크기가 1인 현재 그룹, 인접한 두 그룹, 총 세 그룹의 색깔이 모두 같을 수 있습니다. 따라서 이러한 경우는 한 번 더, 별도로 처리할 필요가 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<pair<int, int>> balls;

void func(int idx1, int idx2, int cnt)
{
	m = min(m, cnt);

	if (idx1 == -1 || idx2 == balls.size())
		return;

	if (balls[idx1].first == balls[idx2].first && balls[idx1].second + balls[idx2].second >= 4)
	{
		cnt -= (balls[idx1].second + balls[idx2].second);
		func(idx1 - 1, idx2 + 1, cnt);
	}

	m = min(m, cnt);
}

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

	cin >> n;
	m = n;

	int color = -1;
	for (int i = 0; i < n; i++)
	{
		int ball;
		cin >> ball;

		if (color == ball)
			balls.back().second++;
		else
		{
			balls.push_back({ ball, 1 });
			color = ball;
		}
	}

	for (int i = 0; i < balls.size(); i++)
	{
		if (balls[i].second == 1 && i != 0 && i != balls.size() - 1)
		{
			if (balls[i - 1].first == balls[i + 1].first && balls[i - 1].second + balls[i].second + balls[i + 1].second >= 4)
				func(i - 2, i + 2, n - balls[i - 1].second - balls[i].second - balls[i + 1].second);
		}

		if (i != 0)
		{
			balls[i].second--;
			balls[i - 1].second++;

			if (balls[i - 1].second >= 4)
				func(i - 2, i, n - balls[i - 1].second);

			balls[i].second++;
			balls[i - 1].second--;
		}
		if (i != balls.size() - 1)
		{
			balls[i].second--;
			balls[i + 1].second++;

			if (balls[i + 1].second >= 4)
				func(i, i + 2, n - balls[i - 1].second);

			balls[i].second++;
			balls[i + 1].second--;
		}
	}

	cout << m << '\n';
	return 0;
}