[백준][C++] 1931 블로그2

1931. 블로그2

20365번: 블로그2

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

간단하고 귀여운 문제였다.

 

형광팬 색깔을 바꾸는 작업을 최대한 덜 해야하므로, 처음에 모든 글을 하나의 색으로 칠한 다음, 칠한 색과 다른 부분을 부분을 작업하면 된다고 생각했다.

그러려면, 최대한 작업량이 많은 색을 처음에 한꺼번에 칠해야 한다.

 

알고리즘 설계

 

1. 파란색으로 바꾸는 작업, 빨간색으로 바꾸는 작업의 수를 각각 계산한다.

 

2. 위에 구한 둘을 비교해서 더 많은 작업이 필요한 색을 처음에 한꺼번에 칠한다.

• 이때 작업량은 1이다.

 

3. 칠하지 않은 색을 모두 칠한다.

• 작업량은 1 + 해당 색의 작업량의 수

 

알기 쉽게 경우를 따져서 그림으로 표현해봤다.

 

코드!

#include <iostream>
using namespace std;

#define RED        1
#define BLUE    2

int main()
{
    int len, red = 0, blue = 0;
    int state = 0;
    char input;

    cin >> len;

    for (int i = 0; i < len; i++)
    {
        cin >> input;

        if (input == 'R')
        {
            // 이전 색이 빨강이 아니라면
            // 색을 바꾸는 작업 횟수 증가
            if (state != RED) red++;
            state = RED;
        }
        else
        {
            if (state != BLUE) blue++;
            state = BLUE;
        }
    }

    // 1(처음에 모두 칠한 횟수) + (더 적은 작업 횟수)
    if (red >= blue)
        cout << 1 + blue;
    else
        cout << 1 + red;
}

간단하게 구현한 것 같다.

 

처음, 한번에 색을 모두 칠하는 방법이 신기하고 효율적인 해결법이라고 생각한다. 재미있었다!