[BOJ/Gold 2] 백준 5577 RBY팡!(C++)

문제 링크

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

5577번: RBY팡!

문제

세로로 N개의 공이 붙어있으며, 각 공의 색은 R(빨강), B(파랑), Y(노랑) 중 하나이다. 플레이어는 한 공의 색을 다른 색으로 바꿀 수 있다. 이러한 변환을 거쳐 동일한 색의 공이 4개 이상 연속되면 그 공들은 팡!하고 터진다. 이 공들이 팡!하고 터지고 난 뒤에는 공들이 위아래로 붙어 다시 연속된 세로열을 유지하며, 팡!하고 터진 후 붙으면서 다시 동일한 색의 공이 4개 이상 연속되면 연쇄적으로 팡!하고 터진다. 이 게임의 목적은 소멸하지 않고 남아있는 공의 수를 최소화하는 것이다. 단, 게임 시작시의 초기 상태에서 동일한 색의 공이 4개 이상 연속된 부분이 없다는 것은 보장된다.

예를 들어, 아래 그림의 왼쪽 상태에서 위에서 6번째 공의 색을 노랑에서 파랑으로 변경하면 파랑공 5개가 연속되므로 팡!하고 터진다. 이후 빨강공 4개가 연쇄적으로 팡!하고 터지므로 3개의 공이 소멸하지 않고 남게된다.

초기 상태에서 N개의 공의 색이 주어졌을 때, 1개 공의 색만 변경하여 연쇄적인 팡! 후에 남아있는 공의 최솟값 M을 구해보자.

입력

첫 번째 줄에 공의 수 N(1 ≦ N ≦ 10000)이 주어진다.

이어지는 N개의 줄에 공의 색에 대한 정보가 연속적으로 주어진다.

공의 색은 1, 2, 3 중 하나로 주어지며, 1은 빨강, 2는 파랑, 3은 노랑을 나타낸다.

출력

소멸하지 않고 남아있는 공의 최솟값 M을 출력한다.

예제 입력 1

12
3
2
1
1
2
3
2
2
2
1
1
3

예제 출력 1

3

예제 입력 2

12
3
2
1
1
2
3
2
1
3
2
1
3

예제 출력 2

12

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 스택
• 재귀

풀이

처음에는 스택을 이용했지만 시간 초과가 뜨는 바람에, 다른 방법을 이용하기로 하였다.

우선 브루트포스 알고리즘을 이용하여, 모든 공의 색깔을 바꿔가면서 공을 제거하고 남는 공의 개수를 확인한다.

다음으로 공을 제거하는데, 재귀를 이용하여, 위아래로 연속된 공의 개수를 파악하고, 연속된 공의 개수가 4개 이상이면 제거하는 과정을 반복하여, 더 이상 제거할 공이 없거나 공의 개수가 3개 이하로 남은 경우 재귀를 종료한다.

모든 공의 색깔을 바꿔가면서 공을 제거하고 남는 공의 개수의 최솟값을 확인한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 10005
#define LL long long
#define INF 1e9

using namespace std;
int N;
vector<int> Ball;
int answer = INF;

int RBY_Pang(int Down, int Up, int Left) {
	int Successive_Down = 1; // 아래로 연속된 공의 개수
	int Successive_Up = 1; // 위로 연속된 공의 개수
	int next_Down = Down; // 아래쪽 인덱스
	int next_Up = Up; // 위쪽 인덱스
	while ((next_Up + 1 < N) && (Ball[next_Up] == Ball[next_Up + 1])) {
		// 범위를 벗어나지 않으면서, 위로 연속된 공의 개수 파악
		next_Up++;
		Successive_Up++;
	};
	while ((next_Down - 1 >= 0) && (Ball[next_Down] == Ball[next_Down - 1])) {
		// 범위를 벗어나지 않으면서, 아래로 연속된 공의 개수 파악
		next_Down--;
		Successive_Down++;
	};
	int Max_Successive;
	if (Ball[Down] == Ball[Up]) { // Down번째 공과 Up번째 공이 같다면 연속된 같은 색깔의 공의 개수를 구한다.
		if (Down == Up) {
			Max_Successive = Successive_Up + Successive_Down - 1;
		}
		else {
			Max_Successive = Successive_Up + Successive_Down;
		}
	}
	else { // 다르다면 아래쪽 연속된 공의 개수 혹은 위쪽 연속된 공의 개수 둘 중 더 큰 값이 최대로 연속된 공의 개수가 된다.
		Max_Successive = max(Successive_Down, Successive_Up);
	}
	if (Max_Successive >= 4) { // 최대로 연속된 공의 개수가 4개 이상이면
		if (Left - Max_Successive < 4) { // 최대로 연속된 공의 개수를 남아 있는 공의 개수에서 빼줬는데 3 이하라면 더 이상 제거할 공이 없다.
			return (Left - Max_Successive);
		}
		// 최대로 연속된 공의 개수를 남아 있는 공의 개수에서 빼줬는데 공이 4개 이상 남아 있다면
		if (next_Down == 0) { // 현재 공의 아래쪽에 더 확인할 공이 없는 경우
			next_Down = next_Up;
		}
		else {
			next_Down--;
		}
		if (next_Up == N - 1) { // 현재 공의 위쪽에 더 확인할 공이 없는 경우
			next_Up = next_Down;
		}
		else {
			next_Up++;
		}
		return RBY_Pang(next_Down, next_Up, Left - Max_Successive); // 공이 4개 이상 남아 있다면 재귀를 사용하여 계속 제거할 공이 있는지 확인
	}
	else { // 아니라면 더 이상 제거할 공이 없다는 뜻이므로, 남아 있는 공의 개수를 return
		return Left;
	}
}

int main() {
	FIRST
	cin >> N;
	for (int i = 0; i < N; i++) {
		int X;
		cin >> X;
		Ball.push_back(X);
	}
	for (int i = 0; i < N; i++) {
		int CurB = Ball[i]; // i번째 공 따로 저장
		int M = INF;
		for (int j = 1; j <= 3; j++) { // i번째 공의 원래 색깔을 제외한 다른 색으로 바꿔가면서 확인
			if (CurB == j) {
				continue;
			}
			Ball[i] = j;
			M = min(M, RBY_Pang(i, i, N));
		}
		answer = min(answer, M);
		Ball[i] = CurB;
	}
	cout << answer << "\n";

	return 0;
}