[BOJ][백준]그리디 알고리즘-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이 된다.

출력

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

 

---

문제를 보자마자 다양한 풀이가 생각납니다. 구간을 나눈 DP나 BFS로 최소 횟수를 구하는 것들이 떠오를 때쯤, N제한이 발목을 잡습니다. 무려 50만, N^2풀이는 아주 넉넉히 시간제한을 초과할 겁니다.문제를 다시 천천히 읽어보면, 생각보다 제한이 까다롭습니다. 다른색깔의 공을 무더기로 넘을 수 있다는 건 그렇다 쳐도, 한번 움직인 공의 색깔은 쭉 유지되어야 한다는 제한도 있습니다. 이 문제를 더 쪼개 볼까요?

예제와 같은(RBBBRBRRR) 공의 배열이 주어질 때, 답은 무조건 이 4가지의 경우 중의 하나로 나타납니다.

 

R만 움직여 RRRRRBBBB 만들기, R만 움직여 BBBBRRRRR 만들기,

B만 움직여 RRRRRBBBB 만들기, B만 움직여 BBBBRRRRR 만들기.

 

그럼 4가지의 경우중 1가지만 방법을 알면, 나머지의 형식이 일치하므로 문제를 풀 수 있게 됩니다. 그럼 R만 움직여 RRRRRBBBB 만들기를 어떻게 접근해야 할까요?

빨간 공을 왼쪽으로 모두 모으기 위해 이것저것 경우의 수를 따지다 보면, 결국

왼쪽에 가까운 빨간 공부터 왼쪽으로 움직여야 모든 이동을 최소화할 수 있게 됩니다. 문제의 요점은 최대한 많은 B뭉치를 점프해야 하는데, 중간에 빨간 공이 껴있다면 1번 만에 이동할 점프를 2번이나 하게 되니까요.

예를 들어볼까요? RBBBRBRRR 배열에서, () 괄호 속에 있는 공을 움직인다고 가정했을 때,

RBBBRB(R) RR이 공을 먼저 움직인다고 가정을 해봅시다. 

RBBBRB(R) RR->RBBB(RR) BRR ->RRRBBBB(RR)->RRRRRBBBB

RBBB(R)BRRR다음은 올바른 이동(최단거리)입니다.

RBBB(R)BRRR->RRBBBB(RRR)->RRRRRBBBB

어떻게 불필요한 점프 횟수가 늘었는지 보이시나요? 

이 점을 알았다면 이제 구현을 해야 하는데, 왼쪽에 가까운 빨간 공부터 왼쪽으로 옮기다 보면

왼쪽에 뭉쳐있는 빨간 공을 제외한 나머지 공들은 모두 1번씩 이동을 하게 된다는 것을 알 수 있습니다. 이를 토대로 구현을 해봅시다. 왼쪽/오른쪽에 뭉쳐있는 빨간 공/파랑 공을 제외한 나머지 빨간 공/파란 공의 최솟값을 구하는 문제가 되었습니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAX_N=500000+2;
int N,Rcnt=0,Bcnt=0;
string s;

int main()
{
    cin>>N>>s;
    for(auto c:s)
    {
        if(c=='R')Rcnt++;
        else Bcnt++;
    }
    int minN=INF,cnt=0,idx=0;
    //left에 R을 모은다.
    while(s[idx++]=='R'){cnt++;}
    minN=min(minN,Rcnt-cnt);
    //right에 R를 모은다.
    idx=N-1,cnt=0;
    while(s[idx--]=='R'){cnt++;}
    minN=min(minN,Rcnt-cnt);
	//left에 B를 모은다.
    idx=0,cnt=0;
    while(s[idx++]=='B'){cnt++;}
    minN=min(minN,Bcnt-cnt);
	//right에 B를 모은다.
    idx=N-1,cnt=0;
    while(s[idx--]=='B'){cnt++;}
    minN=min(minN,Bcnt-cnt);

    cout<<minN;
}

 

약간의 하드코딩이지만, 코드의 줄이 얼마 안 되고, 함수를 구현하는 것이 더 까다로울 것 같으니 이정로만 구현하면 될 것 같습니다. 문제를 풀고 나면 간단해 보이지만, 생각보다 그리디 하게 접근하는 것이 쉽지는 않습니다.