백준 17615 - 볼 모으기

문제 설명

빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.

1. 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
2. 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.

예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.

반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.

일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, R과 B로 이루어진 문자열이 주어지면 문자들을 적절히 밀어 같은 문자들끼리 모이게 만드는 최소 이동 횟수를 구하는 것이다.

 

해당 문제를 풀기 위해서는 2가지만 이해하면 된다.

1. 최종 상태는 두 가지만 존재한다.
2. 이동 횟수는 공들의 묶음으로 표현가능하다.

1번 부터 생각해 보자.

적절한 정렬을 통해 최종 상태를 만든다면 다음과 같은 두 가지 상태밖에 존재하지 않는다.

이를 자세하게 풀면 4개의 경우가 된다.

1. 파란 공을 왼쪽으로 옮긴다
2. 빨간 공을 오른쪽으로 옮긴다
3. 파란 공을 오른쪽으로 옮긴다
4. 빨간 공을 왼쪽으로 옮긴다 

즉, 위의 4개의 경우만 탐색하면 된다.

 

2번에서 말한 이동 횟수는 공들의 묶음으로 표현가능하다는 말은 초기 상태로 주어진 문자열은 연속한 같은 공들의 묶음으로 나타낼 수 있다.

이렇게 표현한 이유는 묶음에 포함된 공이 따로 이동하는 경우는 없기 때문이다.

예를 들어, 2~4번째 B공들을 왼쪽으로 이동한다고 가정해 보자.

그렇다면 우선 2번째 공인 B가 1번째 R공을 넘어 왼쪽으로 이동한다.

이후, 3,4 번째 공이 동일하게 이동한다.

이때, 이동 횟수는 3이 된다.

즉, 공들의 묶음에 포함된 공들의 개수가 해당 묶음이 이동하는 최소 이동 횟수와 일치하게 된다.

 

위에서 언급한 두 가지 사실을 적용하면 다음과 같다.

• 파란 공을 왼쪽에 모을 때, 파란 공묶음을 왼쪽으로 이동시켜 보기
• 파란 공을 왼쪽에 모을 때, 빨간 공묶음을 오른쪽으로 이동시켜 보기
• 빨간 공을 왼쪽에 모을 때, 파란 공묶음을 오른쪽으로 이동시켜 보기
• 빨간 공을 왼쪽에 모을 때, 빨간 공묶음을 왼쪽으로 이동시켜 보기

즉, 기준 점을 잡고 이동시킬 공들의 전체의 개수에서 기준점에 위치한 공묶음의 개수를 빼주면 된다.

기준점에 위치한 공들의 묶음은 이동시킬 필요가 없기 때문이다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

string str;
int N;

struct Ball
{
    Ball(char c, int n) : color(c), num(n) {}
    char color;
    int num;
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> str;

    int redCnt = 0;
    int blueCnt = 0;

    int cnt = 0;
    char current;
    
    vector<Ball> balls;
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == 'R') redCnt++;
        else if (str[i] == 'B') blueCnt++;

        if (i == 0)
        {
            cnt = 1; 
            current = str[i]; 
            continue;
        }

        if (current == str[i]) cnt++;
        else
        {
            Ball temp(current, cnt);
            balls.push_back(temp);
            cnt = 1;
            current = str[i];
        }
    }

    Ball temp(current, cnt);
    balls.push_back(temp);

    int ans = INT_MAX;
    //B가 왼쪽::blue이동
    {
        int moveCnt = blueCnt;

        if (balls[0].color == 'B') 
        {
            moveCnt -= balls[0].num;
        }

        ans = min(ans, moveCnt);
    }

    //R가 왼쪽::red이동
    {
        int moveCnt = redCnt;

        if (balls[0].color == 'R')
        {
            moveCnt -= balls[0].num;
        }

        ans = min(ans, moveCnt);
    }

    //B가 오른쪽:: blue이동
    {
        int moveCnt = blueCnt;

        if (balls.back().color == 'B')
        {
            moveCnt -= balls.back().num;
        }

        ans = min(ans, moveCnt);
    }

    //R이 오른쪽::red이동
    {
        int moveCnt = redCnt;

        if (balls.back().color == 'R')
        {
            moveCnt -= balls.back().num;
        }

        ans = min(ans, moveCnt);
    }

    cout << ans;

    return 0;
}

---