[백준,c++] 20365번 - 블로그2

문제

20365번: 블로그2

 

코드

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    string s; cin>>s;
    
    
    
    char before = 'B';
    bool flag = true;
    int job = 1;
    
    for(int i=0; i<N; i++){
        if(s[i] == before){
            if(flag) job++;
            flag = false;
        }
        else{
            flag = true;
        }
    }
    before = 'R';
    flag = true;
    int job2 = 1;
    
    for(int i=0; i<N; i++){
        if(s[i] == before){
            if(flag) job2++;
            flag = false;
        }
        else{
            flag = true;
        }
    }
    cout<<min(job,job2);
}

 

풀이

1. 연속된 임의의 문제들을 선택한다.
2. 선택된 문제들을 전부 원하는 같은 색으로 칠한다.

문제의 조건은 위와 같습니다. 

문제 풀이 아이디어는 생각보다 간단한데, B와 R가 연속된 색이 몇 번 나오는지만 카운팅 하기만 하면 됩니다. 

한번 예제로 부가설명을 해 보겠습니다.

8
BBRBRBBR

먼저 위 입출력의 경우 R의 연속된 경우는 3번(R, R, R), B의 경우 연속된 경우가 3번(BB, B, BB)입니다. 따라서 둘 중 연속된 수가 적은 수(지금은 둘 다 3으로 동일)에서 +1(다른 색을 사전에 전부 칠했다고 생각했을 경우)을 하면 답이 됩니다. 

6
BRRRRB

위 입출력의 경우 R의 연속된 경우는 1번(RRRR), B가 연속된 경우(B, B)2번 입니다. 따라서 둘 중 연속된 수가 적은 수인 R에다가 처음 B로 전부 칠했다고 가정한+1을 더하면 2가 나오게 되어 정답이 됩니다.