[C++] 17615번: 볼 모으기

링크

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

17615번: 볼 모으기

문제

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

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

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

 

<그림 1>

 

<그림 2>

 

<그림 3>

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

 

<그림 4>

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

입출력 예제

입력

첫 번째 줄에는 볼의 총 개수 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	원래의 제약조건 이외에 아무 제약조건이 없다.

예제 입력 1 복사

9
RBBBRBRRR

예제 출력 1 복사

2

예제 입력 2 복사

8
BBRBBBBR

예제 출력 2 복사

1

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

int main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int answer = 0;
	int countL = 0;
	int countR = 0;
	int r = 0;
	int b = 0;
	int n;
	cin >> n;
	
	vector<char> ball(n);

	// 입력
	for (int i = 0; i < n; i++)
	{
		cin >> ball[i];
		if (ball[i] == 'R')	r++;
		else if (ball[i] == 'B') b++;
	}
	
	// 좌,우측 모서리에 해당 색이 없어서 모든 공을 옮겨야 할 때
	answer = min(r, b);

	// 가장 왼쪽에 있는 색 기준으로 얼마나 연속해서 이어져 있는지
	for (int i = 0; i < n; i++)
	{
		if (ball[i] != ball[0]) break;
		countL++;
	}

	// 가장 왼쪽에 있는 색의 전체 갯수 - 이어져 있는 갯수 = 이어져 있지 않은 수들(옮겨야 할 수)
	if (ball[0] == 'R') answer = min(answer, r - countL);
	else answer = min(answer, b - countL);

	// 가장 오른쪽에 있는 색 기준으로 얼마나 연속해서 이어져 있는지
	for (int i = n - 1; i >= 0; i--)
	{
		if (ball[i] != ball[n-1]) break;
		countR++;
	}

	if (ball[n-1] == 'R') answer = min(answer, r - countR);
	else answer = min(answer, b - countR);

	cout << answer << endl;
}

풀이

• 그리디 알고리즘을 이용해 해결하였다.

RBBBRBRRR

 

공이 다음과 같이 있을 때, 특정 색의 공을 한 쪽으로 몰아넣어야 하니
오른쪽, 왼쪽 끝에 위치한 공의 색을 이용한다.

	// 가장 왼쪽에 있는 색 기준으로 얼마나 연속해서 이어져 있는지
	for (int i = 0; i < n; i++)
	{
		if (ball[i] != ball[0]) break;
		countL++;
	}

우선, 첫 번째로 가장 왼쪽의 공의 색을 기준으로 계산하는데

이 공의 색이 최대 얼마나 이어져 있는지 계산한다.

 

	// 가장 왼쪽에 있는 색의 전체 갯수 - 이어져 있는 갯수 = 이어져 있지 않은 수들(옮겨야 할 수)
	if (ball[0] == 'R') answer = min(answer, r - countL);
	else answer = min(answer, b - countL);

이후 그 색의 전체 갯수에서 이어져 있는 공의 갯수를 빼면

해당 방향으로 옮겨야 하는 공의 갯수를 구할 수 있다.

 

위의 예시에서는 맨 왼쪽에 1개의 빨간 공만 있기 때문에 이어진 공은 1이고
전체 공은 5개 이니, 움직여야 할 공은 5-1 = 4개가 될 것이다.

이후에 맨 오른쪽 공의 색을 기준으로 똑같은 과정을 반복한다.
이어진 공은 3개, 전체는 5개니 5-3 으로 총 2개의 공을 옮겨야 할 것이다.

이렇게 구해진 값 중 작은수를 고르면 답을 구할 수 있다.

RBRRBR

 

하지만 위와 같이 맨 왼쪽, 오른쪽에는 위치하지 않지만 해당 색의 갯수만큼 움직여야 하는 경우가
더 작은수를 가질 경우도 있음을 알아두자.

answer = min(r, b);