[백준 17615] 볼 모으기 (C++)

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

 

문제

---

빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.

1. 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
2. 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.

예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.

 

반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.

 

일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주어질 수도 있으며, 이 경우 답은 0이 된다.

 

출력

---

최소 이동횟수를 출력한다.

 

서브태스크

---

번호배점제한

번호	배점	제한
1	15	N ≤ 10
2	22	N ≤ 1,000
3	14	N ≤ 500,000, 처음 상태에서 모든 파란 공은 연속해서 존재한다.
4	49	원래의 제약조건 이외에 아무 제약조건이 없다.

 

문제 풀이

---

그리디 문제.

 

모든 볼이 같은 색상끼리 모여있어야 한다. 먼저, 하나의 색상을 정해 뒤로 보낸다고 가정한다.

앞에서부터 보낸다고 하면 위의 예시처럼 그 뒤에 다른 색상이 있을 경우 또 옮겨야 한다. 뒤에서부터 옮기면 이런 문제가 발생하지 않는다.

만약 옮기기로 선택한 색깔의 공의 맨 마지막 공과 색깔이 같다면 아예 옮길 필요가 없을 수도 있고, 옮겨야 할 필요가 있을 수도 있다. 하나라도 다른 색깔의 공이 있다면 그 앞에 있는 모든 맨 마지막 공과 색깔이 같은 공을 옮겨야 하기 때문이다. 위의 예시에서는 R을 선택한 경우이고, B가 있다면 그 앞에 있는 R을 모두 옮겨야 한다. 따라서 이 경우는 맨 마지막 B(=맨 마지막 공과 색깔이 다른 공)의 위치를 찾아 그 앞에 있는 R(=맨 마지막 공과 색깔이 같은 공)을 모두 맨 마지막 B 뒤로 옮겨주면 된다. 다시 말해 맨 마지막 B 이전에 존재하는 R의 개수를 찾으면 이 경우의 이동 횟수가 된다.

 

만약 옮기기로 선택한 색깔의 공이 맨 마지막 공과 색깔이 다르다면 뒤에서부터 옮겨주면 된다. 따라서 맨 마지막 공과 색깔이 다른 공의 개수가 이 경우의 이동 횟수가 된다.

 

위와 비슷하게 색상을 하나 정해 앞으로 보낸다고 가정하는 것도 구할 수 있다. 이 네가지 경우를 모두 구한 후 최솟값을 구한다면 정답이 된다.

 

아래는 코드.

 

#include <iostream>
#include <algorithm>
using namespace std;
int N;
string str;

int sendBack()
{
	int diffCount = 0;
	int sameCount = 0;
	int lastDiffIndex = 0;
	for (int i = N - 1; i >= 0; i--)
	{
		if (str[i] != str[N - 1])
		{
			lastDiffIndex = i;
			break;
		}
	}
	for (int i = 0; i < N; i++)
	{
		if (str[i] != str[N - 1])
		{
			diffCount++;
		}
		else if (i < lastDiffIndex)
		{
			sameCount++;
		}
	}
	return min(diffCount, sameCount);
}

int sendFront()
{
	int diffCount = 0;
	int sameCount = 0;
	int firstDiffIndex = N-1;
	for (int i = 0; i < N; i++)
	{
		if (str[i] != str[0])
		{
			firstDiffIndex = i;
			break;
		}
	}
	for (int i = 0; i < N; i++)
	{
		if (str[i] != str[0])
		{
			diffCount++;
		}
		else if (i > firstDiffIndex)
		{
			sameCount++;
		}
	}
	return min(diffCount, sameCount);
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N;
	cin >> str;
	cout << min(sendBack(), sendFront()) << "\n";
	return 0;
}