백준 BOJ 17615 - 볼 모으기

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

17615번: 볼 모으기

R이랑 B 두가지 색을 가진 공을 적절하게 이동시켜서 같은색끼리 모으는 문제이다.

 

처음 보고 들었던 생각은

R에 0

B에 1 이런느낌으로 숫자할당을 해서

swap 정렬횟수를 세는 inversion counting 유형인줄 알았다.

하지만 인접한 두 원소간의 교환이 아니라서 해당 가설(?) 은 부정됨.

 

두번째로 생각했던 것은

<그림 3>에서처럼

R이 뭉쳐져 있는 쪽으로 남은 R을 이동시키는게

이동 연산횟수에서 이득을 볼 것이라는 생각을 했었다.

 

그래서

왼쪽에서 시작하는 R의 갯수 => sR

왼쪽에서 시작하는 B의 갯수 => sB

오른쪽에서 '' => eR

오른쪽에서 '' => eB

 

이렇게 네 가지 경우에 대한 숫자를 세줬고,

 

어떤 특정한 끝 부분에 N개의 연속한 공이 모여있다면

전체 M개의 같은 색상 공들에 대해서

M-N번 이동 연산을 해줘야 한쪽으로 모을 수 있기 때문에,

각 경우에 대해서 M-N을 계산하고

그 최솟값을 출력해주면 된다.

 

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

int main(){
	int N;
	string s;
	cin >> N;
	cin >> s;
	
	int sR = 0, sB = 0;
	int eR = 0, eB = 0;
	int cR = 0, cB = 0;
	
	for(int i=0; i<N; i++){
		if(s[i] == 'R') cR++;
		if(s[i] == 'B') cB++;
	}
	
	while(sR < N && s[sR] == 'R') sR++;
	while(sB < N && s[sB] == 'B') sB++;
	while(eR < N && s[N-1-eR] == 'R') eR++;
	while(eB < N && s[N-1-eB] == 'B') eB++;
	
	int ans = min({cR-sR, cB-sB, cR-eR, cB-eB});
	cout << ans;
	return 0;
}