[그리디 #12] BOJ 20365 - 블로그2

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

20365번: 블로그2

 

1차 시도

예제에 있는 문장을 보고 어그로(?)에 끌려 이상하게 접근을 했다.

 

하지만, 1~7번 문제를 파란색, 3번을 빨간색, 5번을 빨간색, 8번을 빨간색으로 순서대로 칠한다면 작업 횟수는 4번으로 가장 적다.

 

위 문장에서 먼저 파란색으로 칠한 다는 것 때문에, 무조건 밑 바탕을 칠하고 가야한다고 생각했다.

따라서, 다음과 같은 알고리즘을 설계함.

 

1. 가장 많은 색을 바탕으로 깔고 들어간다.

2. 반대되는 색을 칠하며, cnt를 +1 한다.

 

그러나 위 방법에 반례가 존재한다.

 

4
RBBR
// 정답: 2

6
RBBBBR
// 정답: 2

 

위 처럼 가운데 색으로 먼저 칠하고, 나머지를 칠할 때 cnt를 +1 하면

3이 나오기 때문에 틀린다.

 

 

정답

따라서, 바탕을 칠할때 가장 많이 칠해진 색 대신, 처음으로 오는 색으로 칠해야 한다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

int n;
string str;
vector<int> v;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int res = 1;

	cin >> n;
	cin >> str;
	
	char firstChar = str[0];
	bool flag = false;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] != firstChar) {
			flag = true;
		}
		else {
			if (flag) {
				flag = false;
				res++;
			}
		}
	}
	if (flag) res++;
	
	cout << res;
}