[백준 / C++] 17615번: 볼 모으기 (그리디 알고리즘)

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

17615번: 볼 모으기

난이도: solved.ac 실버 1

 

접근 방법

결론: R과 B를 각각 맨 앞으로 옮기는 경우, 맨 뒤로 옮기는 경우 이렇게 총 4가지 경우의 수를 구해야 한다.

 

아래의 경우를 보자.

 

RRRBBBRRBBRBRR

 

R의 총 개수는 8개이고 맨 앞에 R이 3개 연속으로 있고 맨 뒤에는 R이 2개 연속으로 있다.

R을 모두 맨 앞으로 몰아넣으려면 뒤에 있는 5개(전체 R의 개수 - 맨 앞에 있는 R의 개수)의 R을 옮겨야 하므로 옮기는 횟수는 5가 된다.

R을 모두 맨 뒤로 몰아넣으려면 앞에 있는 6개(전체 R의 개수 - 맨 뒤에 있는 R의 개수)의 R을 옮겨야하므로 옮기는 횟수는 6이 된다.

 

이번에는 B를 기준으로 보자.

맨 앞으로 B를 모두 몰아넣으려면 뒤에 있는 6개(전체 B의 개수 - 맨 앞에 있는 B의 개수(=0))의 B를 옮겨야 하므로 옮기는 횟수는 6이 된다.

맨 뒤로 옮기는 경우도 마찬가지로 옮기는 횟수는 6회(전체 B의 개수 - 맨 뒤에 있는 B의 개수)이다.

 

따라서 위의 네 가지 경우에서 최소로 옮기는 횟수는 5회가 된다.

 

위와 같이 옮기는 횟수를 구하기 위해서 알아야할 것은 다음과 같다.

1. 전체 R과 B 각각의 개수

2. 맨 앞에 있는 연속된 R의 개수 또는 맨 앞에 있는 연속된 B의 개수

3. 맨 뒤에 있는 연속된 R의 개수 또는 맨 뒤에 있는 연속된 B의 개수

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, flag = 0, red = 0, blue = 0;
	cin >> N;
	string str;
	cin >> str;

	// 각각 맨 앞의 R, B의 개수, 맨 뒤의 R, B의 개수
	int st_R = 0, st_B = 0, en_R = 0, en_B = 0;
	if (str[0] == 'R') {
		red++;	st_R++;
	}
	else {
		blue++;	st_B++;
	}

	for (int i = 1; i < N; i++) {
		// 맨 앞 색과의 연속이 끊어지는 여부를 flag로 구분해주었다.
		if (!flag) {
			// flag = 0: 첫 공을 기준으로 지금까지 색이 바뀌지 않았을 경우
			if (str[i] == str[0] && st_R) {
				// 빨간색일 때
				red++;	st_R++;
			}
			else if (str[i] == str[0] && st_B) {
				// 파란색일 때
				blue++;	st_B++;
			}
			else {
				// flag = 1: 색이 바뀐 경우
				if (str[i] == 'R') {
					en_R++;	red++;
				}
				else {
					en_B++; blue++;
				}
				flag = 1;
			}
		}
		else {
			if (str[i] == 'R') {
				en_B = 0;
				en_R++;	red++;
			}
			else {
				en_R = 0;
				en_B++;	blue++;
			}
		}
	}
	int min = red - st_R;	// 맨 앞으로 R을 다 옮기는 경우
	if (blue - st_B < min)	// 맨 앞으로 B를 다 옮기는 경우
		min = blue - st_B;
	if (red - en_R < min)	// 맨 뒤로 R을 다 옮기는 경우
		min = red - en_R;
	if (blue - en_B < min)	// 맨 뒤로 B를 다 옮기는 경우
		min = blue - en_B;
	cout << min;
}

코드 제출 결과