백준 17615 볼 모으기

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int ans;
    cin >> n;

    string s;

    cin >> s;


    char temp = s[0];
    int tcnt = 1;

    //같은 색상끼리 뭉쳐있는 경우
    vector<int> cnt;

    for (int i = 1; i < n; i++) {

        if (temp == s[i]) {
            tcnt++;
        } else {
            temp = s[i];
            cnt.push_back(tcnt);
            tcnt = 1;
        }
    }

    cnt.push_back(tcnt);


    int acnt = 0;
    int bcnt = 0;

    if (cnt.size() % 2 == 1) {
        if (cnt.front() > cnt.back()) {
            for (int i = 1; i < cnt.size(); i++) {
                if (i % 2 == 1) {
                    acnt += cnt[i];
                } else {
                    bcnt += cnt[i];
                }
            }
        } else {
            for (int i = 0; i < cnt.size() - 1; i++) {
                if (i % 2 == 1) {
                    acnt += cnt[i];
                } else {
                    bcnt += cnt[i];
                }
            }

        }
    } else {
        for (int i = 1; i < cnt.size() - 1; i++) {
            if (i % 2 == 1) {
                acnt += cnt[i];
            } else {
                bcnt += cnt[i];
            }
        }
    }

    ans = min(acnt, bcnt);

    cout << ans;


    return 0;
}

1. 문제

빨간 볼과 파란 볼의 일직선 상의 위치가 주어진다. 이를 다음과 같은 규칙으로 옮겨 같은 색상의 볼끼리 인접하게 놓이도록 하려고 한다.

• 바로 옆에 같은 색상의 볼이 있으면 모두 뛰어넘을 수 있다.
• 옮길 수 있는 볼의 색은 한가지이다.

이 때, 볼의 최소 이동횟수를 구하라.

2. 풀이

예제의 그림이다. 그림 2의 과정으로 그림 3으로 만들면 그림 3에서는 B가 뭉쳐지므로 왼쪽의 R이 모두 뛰어넘을 수 있다. 이를 기본으로 그리디하게 풀 수 있다.

 

    char temp = s[0];
    int tcnt = 1;

    //같은 색상끼리 뭉쳐있는 경우
    vector<int> cnt;

    for (int i = 1; i < n; i++) {

        if (temp == s[i]) {
            tcnt++;
        } else {
            temp = s[i];
            cnt.push_back(tcnt);
            tcnt = 1;
        }
    }

    cnt.push_back(tcnt);

우선 각 색상 당 몇 개의 볼이 뭉쳐있는 지 확인한다.

이런 느낌의 결과가 배열에 저장된다.

 

다음은 각 케이스를 나누어 풀이한다.

    int acnt = 0;
    int bcnt = 0;

    if (cnt.size() % 2 == 1) {
        if (cnt.front() > cnt.back()) {
            for (int i = 1; i < cnt.size(); i++) {
                if (i % 2 == 1) {
                    acnt += cnt[i];
                } else {
                    bcnt += cnt[i];
                }
            }
        } else {
            for (int i = 0; i < cnt.size() - 1; i++) {
                if (i % 2 == 1) {
                    acnt += cnt[i];
                } else {
                    bcnt += cnt[i];
                }
            }

        }
    }

 우선 위 연산으로 홀수 개의 수가 나오는 경우이다. 이 때는 가장 바깥 쪽이 같은 색상의 볼일 것이다. 

 여기서 cnt.front가 cnt.back보다 더 클 경우 얘를 두고 나머지의 볼을 이용하는 데, front와 같은 색상의 볼을 왼쪽으로 옮기는 경우와 다른 색상의 볼을 바깥쪽으로 옮기는 경우로 나눌 수 있다. 반대로 작을 경우 back을 그대로 두고 나머지 볼을 옮기는 경우로 나눌 수 있다. 

같은 색상의 볼을 옮기는 경우

다른 색상의 볼을 옮기는 경우

위의 두 가지 경우 중 더 작은 경우를 선택할 것이다.

else {
        for (int i = 1; i < cnt.size() - 1; i++) {
            if (i % 2 == 1) {
                acnt += cnt[i];
            } else {
                bcnt += cnt[i];
            }
        }
    }

cnt의 크기가 짝수일 경우, 앞의 볼 색상과 뒤의 볼 색상은 서로 다른 색상일 것이다. 이 때, 앞의 색상의 볼을 앞으로 모두 옮기는 경우와 뒤의 색상의 볼을 뒤로 모두 옮기는 경우로 나눌 수 있다. 

앞의 색상의 볼을 앞으로 옮기는 경우

뒤의 색상의 볼을 뒤로 옮기는 경우

두 경우 모두 맨 앞과 맨 뒤의 볼 뭉치는 그대로 있으므로 그 사이의 볼의 개수를 계산한다.

 

    ans = min(acnt, bcnt);

    cout << ans;

각 두 가지 케이스 중 더 작은 것을 선택하면 최솟값을 구할 수 있다.