백준 17615. 볼 모으기

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

17615번: 볼 모으기

 

볼을 모두 옮겼을때 좌측에 빨강볼, 우측에 파랑볼 or 좌측에 파랑볼, 우측에 빨강볼이 될것이다.

 

4가지 케이스로 나눠봤다.

1. 좌측에 빨강볼, 빨강볼을 옮김

2. 좌측에 파랑볼, 파랑볼을 옮김

3. 좌측에 빨강볼, 파랑볼을 옮김

4. 좌측에 파랑볼, 빨강볼을 옮김

 

인풋이 다음과 같다면

RBBBRBRRR

1	2	3	4	5	6	7	8	9
R	B	B	B	R	B	R	R	R

 

1번) 좌측에 빨강볼, 빨강볼 옮김

1. 5번 볼을 좌측에 옮김
2. 7번 볼을 좌측에 옮김
3. 8번 볼을 좌측에 옮김
4. 9번 볼을 좌측에 옮김 

2번) 좌측에 파랑볼, 파랑볼을 옮김

1. 2번 볼을 좌측에 옮김
2. 3번 볼을 좌측에 옮김
3. 4번 볼을 좌측에 옮김
4. 6번 볼을 좌측에 옮김

3번) 좌측에 빨강볼, 파랑볼을 옮김 (우측부터 탐색)

1. 6번 볼을 우측으로 옮김
2. 4번 볼을 우측으로 옮김
3. 3번 볼을 우측으로 옮김
4. 2번 볼을 우측으로 옮김

 

4번) 좌측에 파랑볼, 빨강볼을 옮김

1. 5번 볼을 우측으로 옮김
2. 1번 볼을 우측으로 옮김

 

잘 살펴보면 각각의 케이스의 갯수는 옮기는 색 볼의 총 갯수 - 옮기는 색 볼이 옮기는 쪽에 붙어 있는 갯수다.

 

예를들어 1번은 옮기는색 볼이 R이고, 옮기는 쪽이 좌측이므로

옮기는 색 볼의 총 갯수(5) - 옮기는 색 볼이 옮기는 쪽에 붙어 있는 갯수(1) = 4

 

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int n;
string ball;

int main()
{
    cin >> n;
    cin >> ball;

    // R,B의 총 갯수
    int rCnt = 0, bCnt = 0;
    for(int i = 0; i < n; i++)
    {
        if(ball[i] == 'R') rCnt++;
        else bCnt++;
    }

    // 왼쪽, 오른쪽에 연속으로 붙어있는 같은색 볼의 갯수
    char left = ball[0];
    int leftCnt = 1;
    for(int i = 1; i < n; i++)
    {
        if(ball[i] == left)
            leftCnt++;
        else
            break;
    }

    char right = ball[n-1];
    int rightCnt = 1;
    for(int i = n-2; i >= 0; i--)
    {
        if(ball[i] == right)
            rightCnt++;
        else
            break;
    }

    // 왼쪽, 오른쪽에 연속으로 붙어있는 볼들의 수
    int leftR, leftB, rightR, rightB;
    if(left == 'R')
    {
        leftR = leftCnt;
        leftB = 0;
    }
    else
    {
        leftB = leftCnt;
        leftR = 0;
    }
    if(right == 'R')
    {
        rightR = rightCnt;
        rightB = 0;
    }
    else
    {
        rightB = rightCnt;
        rightR = 0;
    }


    // left:R, move:R
    int RR = rCnt - leftR;
    // left:B, move:B
    int BB = bCnt - leftB;
    // left:B, move:R
    int BR = rCnt - rightR;
    // left:R, move:B
    int RB = bCnt - rightB;

    // 최솟값 탐색
    int ans = min({RR,BB,BR,RB});

    cout << ans;



}