[백준] 17615번: 볼 모으기

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

17615번: 볼 모으기

간단히 말하자면 빨간 볼, 파란 볼 분리 문제이다.

 

크게 결과의 경우의 수는 4가지 이다.

1. 빨간 볼을 움직여서 오른쪽으로 모은다.

2. 빨간 볼을 움직여서 왼쪽으로 모은다.

3. 파란 볼을 움직여서 오른쪽으로 모은다.

4. 파란 볼을 움직여서 왼쪽으로 모은다.

 

그런데 여기서 더 나아가서 어떤 게 효율적일지 고민해보면 어차피 끝에 이왕 모여 있는 볼들을 활용하면 좋겠다는 생각이 자연스레 든다.

그 과정에서 반드시 끝에 있는 공을 안 쓰고 효율적이지 않은 정답도 있지 않을까 고민해보게 된다.

정답은 '그럴 수 없다'이다.

왜냐하면 만에 하나 단 하나의 다른 색의 공이 끝에 있다면 그 방향으로 움직여서 절대 승산을 볼 수 없다.

모든 공을 하나씩 그 공을 건너뛰는 일을 수행해야 하기 때문이다.

문제에서 하나의 색의 공만 움직일 수 있다한 점을 감안하면 딱 봐도 비효율적인 행위임이 감이 온다.

따라서 효율적인 이동을 위해 기본적으로 끝 색깔에 맞추어 공을 이동하는 것이 효율적이다.

즉 이 문제는 이렇게 Greedy하게 양 끝 쪽에 이미 공이 많이 있는 경우를 골라 최대한 적은 수의 남은 공들을 움직이는 방안으로 풀면 된다.

 

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, red_cnt = 0, blue_cnt = 0, answer = 0, cnt = 0;
    string str;
    cin >> n;
    cin >> str;
    if(n == 1) {
        cout << 0 << '\n';
        return 0;
    }
    
    for(int i = 0;i < n;i++) {
        if(str[i] == 'R') red_cnt++;
        else blue_cnt++;
    }
    
    if(red_cnt == 0 || blue_cnt == 0) {
        cout << 0 << '\n';
        return 0;
    }
    
    answer = min(red_cnt, blue_cnt);
    
    for(int i = 0;i < n;i++) {
        if(str[i] != str[0]) break;
        cnt++;
    }
    
    if(str[0] == 'R') {
        answer = min(answer, red_cnt - cnt);
    }
    else {
        answer = min(answer, blue_cnt - cnt);
    }
    
    cnt = 0;
    for(int i = n - 1;i >= 0;i--) {
        if(str[i] != str[n - 1]) break;
        cnt++;
    }
    
    if(str[n - 1] == 'R') {
        answer = min(answer, red_cnt - cnt);
    }
    else {
        answer = min(answer, blue_cnt - cnt);
    }
    
    cout << answer << '\n';
}