BOJ 17615. 볼 모으기

문제 링크 

 

 문제 풀이

 문제에서는 볼들의 배열이 주어졌을 때 같은 색깔의 볼들을 한 쪽으로 모으는 최소 이동 횟수를 요구하고 있다. 

 

 처음 봤을 땐 왼쪽으로 빨간색을 다 모으는 경우, 파란색을 다 모으는 경우, 오른쪽으로 빨간색을 다 모으는 경우, 파란색을 다 모으는 경우 모두 나눠서 반복문을 4번 돌아 구한 다음, 최소를 출력하려고 했다. 근데 더 생각해보니 왼쪽이랑 오른쪽으로 총 2번만 반복문을 돌아도 다 구할 수 있었다.

 

 핵심 아이디어는 어떤 방향으로 어떤 색을 모을 때의 최소 조작 횟수를 세는 것이 그 방향으로부터 연속하지 않는 그 색의 볼 개수를 세는 것과 같다는 것이다. 예를 들어서 문제의 예시에서 R을 모두 왼쪽으로 넘기는 최소 조작횟수는

왼쪽 끝에 연속해 있지 않은 R들의 개수와 같다. 그리고 또 이것은 R의 전체 개수에서 왼쪽 끝에 연속한 R의 개수를 뺀 것과 같다. 그리고 여기서 또 왼쪽에는 R이 연속하므로 왼쪽에 연속한 B의 개수는 0이라는 것도 알 수 있다.

 

 그래서 전체 R, B의개수와, 각 방향에서 연속한 볼들의 개수를 세주고, 적절히 빼준 다음, 최솟값을 출력해주면 된다.

 

 시행 착오

 처음 생각했던 대로 코드를 짰는데 틀려서 반례를 찾아봤더니 

95771
RBRRBBRRRBRRBBRBRBBRBRRBRRBBBBBRRBRBBBBBBRBRBRRBRBBBRRBBBBBRRRBBBRRBRBRRBRRBBRBBRBBRBRBBBRBBRBRRBRBBRRRBBRBRRRRRBRBBRBRBRRBBBBRBRRRBBRBRRRRBBRRRRBRBBRRBBBBBBRRBRRBBBBBBBBRBRBBRBRRBRBRRBBRBRRRBBRBBRBRBBRBBRRRRBRBBBRBBRRBBBBRRRRRBRRRBBRBBRRRBRBRRRBBBBRRBBBRBBBBRBBBBRRBBBBRRBBBBBRRRBRBBBRRBBBRRRBRRRBBRBRRBBRBBBRBBRRRRBBRBBBRRRBRBRRRBRRBRRRBBRBRRBRRBBBRRRBBRBBRBRRRBRRRBRBBRRRRRRRRBRBBRRBRBBBBBRRRRRRRRRBBBBBBRBBRBBRRBBRBRBBBBBBRBBBBBRRBRRRRBRRBRBRRRRBRRBBBBBRBBBBBRRBRRBBRBBBRBRBRBBBBRRRRBRRRRRBBBBRBBBBBRBBBRBBBRRBRBBBRBBBRRBRRRBRRBBBRRRBBBRRRBBBRBBRBBBBRRRBBRRBRRRBRRBBRBRRBRBRBRBBBRRRRRBBRRBRBBRBBBRBBBRBBRRRBBRRRBBBBBRRRRBBRBBRBBRRRRRRBRRRRBRBRBRRRBRRRBBRBRBRBBRBRBBRBRRBRRBRBBBRBRRBRBBRBRRBBBBBRBBRBBRBBRBBBBRRBRRBBRBRRRRRBBBRRBBRBBBBBBRRRRRRBBRBRRBRBRRBBBRRRBBBBRRBRRRBBBRRBRBBBRBRRBBRRRRBBRRRBRRBBRBBRRBRRRRRBBRRRRRRBBBBBRBBBRRRRRBBBRBBBRBBRBRBRRRRBRBRBBRRRRBRRRBRRRBRBRBRRRBBRRRRRBBRBBRBBRBRBBBBRBBRRBRRRBBBRRBRRRBRBBRRBBBBRBBRRRBRBBRRRRBRBRBBBRBRRRRBRRBBBBBRRRRBRBRRRBRRBRBRBBBRRBRBRRBRBBRRRBBBBRRRRBBRBBRBRBBBBRBBBRBBRRRRRRRRBBRBRRRRBRBRRRBBBRRBRRRRBRBBRRRBRRRRBRRBRRBRBRBBRRRRBBBRBRBRBBBBBRBBBBRBRRBRRBRBRRRBBRRRBBBRRBBBRBBBBBBRRBBBBBRRRRRRRRBRRRBBRBBBBBBRRBRBRBRBRBRRRRBRRRBRRRRRRBBRBRBRBRBRRBRRBBBBRRBBRBBBBBBRBBBRBBBBBBBRBRRRBBBBBRBBRBBBRBBRRBRBBRBRRBRBRRRBRBRBRBRRBBRRBBBRRRRBRRRRRRRBRBBBBBRBRRBRBBRRRRRRRRBRRBRBRRBRBBBBRRRRRBRBRRBBRRBRBRRRRRRBBRBBRRBRRRBBRRBRRRRBRRRBBRRBBBBRBBBBBBBRRRRBBRRBBBBRRRBRRRRBBRRBBBBRRBBBRBBRBRBRRBBRRBRRBRRBRBRBBRBRRRBBBBBRRBBBRBBRBRBRBBRRBRBBBBBRBBBRBRBRBBRBBRBRRRBBRRBRBRRRRBBRRRRRRBBRRBBRBRRBRRBRRRRRBRBRRBBRBRRBRRBRBBRBBRBRRRRBRBBBBBBRBRBBRBRRBBBBBRRBRBBRBBBBBBRBBBBBRBBRBRRBBRRRRBBBRRRBRRRBRBBBBRRRBRRRBBBBBBBBBBBBRBRRRRBBRBBRRRBBBBRBBBRBBRBRRBBBRBRBRBBBBBBRRRBBBBBRBRRBRRBBRBRBBRBBBBBRRRBRBBBBBBRBBBRRRRBBBRRBBBRBRBBBRBRBBRBRRRBRBRRRBRBRRRBBBBRBRRRBBRRRRRBBBBRBBRBRBRRBRBRBRBBBBBRRRBBBRRRBRBBBRRBBBBRRBBBRBRBBRRBBRRRRBBRRRBBRRBBRRRBRRRRRBRRBRRRBBRRRBRRRBRRBBRRRRBRRBBRRRBRBBBRRBBRRRRBRRRRBRRBBBBRBBRBBBRRBBBRRRRRBBBBRRRBRBBRRBRRBBRRRBRBBBBRRRRR

이런 더러운 반례가 1차이로 틀려서 멘탈이 나갔었다. 계속 코드를 보고 또 보고 하다가,

flag = isRed[1];
for(i=2;i<=N;i++)
{
    if(flag==true)
    {
        RL++;
        if(isRed[i] != flag)
        {
            BR = 0;
            break;
        }
    }
    else
    {
        BL ++;
        if(isRed[i] != flag)
        {
            RR = 0;
            break;
        }
    }
}

 이 부분에서 isRed가 flag랑 달라지지 않고 쭉 flag와 같은 값일 때 오류가 난다는 것을 알았고 수정하였다. 덕분에 설계를 꼼꼼히 하자는 교훈을 얻은 것 같다.

 

 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    int R=0,B=0,N,RL=0,RR=0,BL=0,BR=0,i;
    char chr;
    bool flag;
    
    cin>>N;
    
    bool isRed[N+1]={false,};
    
    for(i=1;i<=N;i++)
    {
        cin>>chr;
        if(chr=='R')
        {
            R++;
            isRed[i] = true;
        }
        else
        {
            B ++;
        }
    }
    
    flag = isRed[1];
    
    for(i=1;i<=N;i++)
    {
        if(flag==true)
        {
            
            if(isRed[i] != flag)
            {
                BL = 0;
                break;
            }
            else
            {
                RL++;
            }
        }
        else
        {
            
            if(isRed[i] != flag)
            {
                RL = 0;
                break;
            }
            else
            {
                BL ++;
            }
        }
    }
    
    flag = isRed[N];
    for(i=N;i>=1;i--)
    {
        if(flag==true)
        {
            
            if(isRed[i] != flag)
            {
                BR = 0;
                break;
            }
            else
            {
                RR++;
            }
        }
        else
        {
            
            if(isRed[i] != flag)
            {
                RR = 0;
                break;
            }
            else
            {
                BR ++;
            }
        }
    }
    
    cout<<min({R-RL,R-RR,B-BL,B-BR});
}