[BOJ] 블로그2 20365번 C++

 

 

문제

neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한다. 일우는 각 문제를 칠할 때 아래와 같은 과정을 한 번의 작업으로 수행한다.

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

예를 들어, 각 문제를 위와 같은 색으로 칠하려고 할 때, 1~2번 문제를 파란색, 3번을 빨간색, 4번을 파란색, 5번을 빨간색, 6~7번을 파란색, 8번을 빨간색으로 칠하는 작업을 순서대로 수행하면 6번의 작업을 거쳐야 한다. 하지만, 1~7번 문제를 파란색, 3번을 빨간색, 5번을 빨간색, 8번을 빨간색으로 순서대로 칠한다면 작업 횟수는 4번으로 가장 적다.

일우는 매일 500,000문제까지 시도하기 때문에, 이 작업이 꽤나 귀찮아지기 시작했다. 그래서 가장 효율적인 방법으로 위 작업을 수행하기를 원한다. 일우를 도와 각 문제를 주어진 색으로 칠할 때 필요한 최소한의 작업 횟수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 색을 칠해야 하는 문제의 수 N (1 ≤ N ≤ 500,000)이 주어진다.

둘째 줄에 N개의 문자가 공백 없이 순서대로 주어진다. 각 문자는 i번째 문제를 어떤 색으로 칠해야 하는지를 의미하며, R은 빨간색, B는 파란색을 나타낸다. 그 외에 다른 문자는 주어지지 않는다.

출력

첫째 줄에 일우가 주어진 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값을 출력하라.

 

접근 방식

 

처음에는 단순하게 접근했다

BBRBRBBR

입력값이 다음과 같을 때 output 이 4가되려면 결국

B, R 중에 더 작은값에 + 1(한가지로 색을 칠하는 경우)를 더해주면 되기 때문에다

 

여기서도 B는 6, R은 3이므로 최소로 작업할 수 있는 횟수는 4이다.

 

하지만, 이렇게 접근을 하니 B,R이 같은 값을 가질 때가 문제였다

 

6
BRBRBR

 

이 인풋으로는 풀리지만

 

6
BBRRRB

6
BBBRRR

이럴때는 최소값이 달라진다.

둘다 최소로 2 작업횟수를 가질 수 있다

 

그렇게 고민하다가 다른 분들 풀이를 찾아보니 간단하게 풀 수 있는 방법을 알았다

압축을 사용하는 것이다.

BBBRRR => BR로 압축하면 어쩌피 연속되어 있으면 한 번에 칠할 수 있으므로 최소 횟수는 2가 나온다

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int main() {
    int N; cin>>N;
    string str; cin>>str;
    int cnt_B = 0, cnt_R = 0;
    string s = "";
    string tmp = "";
    for(auto c : str) {
        if(tmp.size() == 0) tmp += c;
        else {
            if(c == 'B') {
                if(tmp[0] == 'B') tmp += c;
                else {
                    s += tmp[0];
                    tmp = "B";
                }
            }
            else {
                if(tmp[0] == 'R') tmp += c;
                else {
                    s += tmp[0];
                    tmp = "R";
                }

            }
        }
    }
    s += tmp[0];


    for(auto c : s) {
        if(c == 'B') cnt_B++;
        else cnt_R++;
    }

    if(cnt_B > cnt_R) cout<<cnt_R + 1;
    else cout<<cnt_B+1;
}