[백준] 블로그2 C++

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

---

해설

우선 언제 최소의 횟수가 되는지 부터 생각을 했다.

모든 문제를 파란색으로 다 칠하고 나머지 빨간색에 해당하는 부분들을 빨간색으로 칠하면 최소가 되지 않을까? 생각했는데 문제는 빨간색이 더 많을 때였다

따라서 빨간색이 더 많은지 파란색이 더 많은지 살펴보고 더 작은 개수를 차지하는 색으로 일부분을 칠해주어야한다.

 

본인은 처음에 파란색으로 일부분을 칠할 때, 빨간색으로 일부분을 칠할 때, 둘다 계산을 해준다음에 이중 최소를 출력했는데, 이렇게 하지않고 밑줄 친 부분대로 해주어도 상관없다.

 

---

코드

 

본인 코드

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

// 빨간색으로 색을 칠하는 것과 파란색으로 색을 칠하는 것중 최소 값을 출력한다.ㅃ
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; cin >> n;
    string str; cin >> str;
    int bcnt = 0, rcnt = 0;
    for (int i = 0; i < n; ++i)
    {
        if (str[i] == 'B') ++bcnt;
        else if (str[i] == 'R') ++rcnt;
    }

    int ret = 0; int bret = 0; int rret = 0;
    if (bcnt == 0) cout << 1;
    else if (rcnt == 0) cout << 1;
    else
    {
        bcnt = 0; rcnt =0;
        for (int i = 0; i < n; ++i)
        {
            if (str[i] == 'B') // 빨간색으로 일부분을 칠한다는 가정
            {
                ++bcnt;
                if (rcnt != 0)
                {
                    ++rret;    // 예를 들어 RRB...BBR 에서 3번째 B를 만난 순간 빨간색으로 일부분을 칠하는 횟수를 하나 늘린다.
                    rcnt = 0;    
                }
            }    
            else if (str[i] == 'R') // 파란색으로 일부분을 칠한다는 가정
            {
                ++rcnt;
                if (bcnt != 0)
                {
                    bcnt = 0;
                    ++bret;
                }
            }
        }

        if (bcnt != 0) ++bret;
        if (rcnt != 0) ++rret;

        cout << min(bret, rret) + 1; // + 1은 바탕색을 칠하는 경우
    }
}

 

좀더 개선한 코드

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

// BBRBRBBR 인경우 R과 B중 개수가 더 많은 것을 바탕색으로 칠하고 개수가 더 작은 문자로 일부분을 칠한다.
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, b = 0, r = 0;
    string str;
    cin >> n >> str;
    if (str[0] == 'B') ++b;
    else ++r;
    for (int i = 1; i < n; ++i)
    {
        if (str[i] == 'B' && str[i - 1] == 'R') ++b;
        if (str[i] == 'R' && str[i - 1] == 'B') ++r;
    }
    cout << min(r, b) + 1;
}