문제 풀이

문제를 모두 B로 칠할 때와 R로 칠할 때 두 가지 경우의 수를 고려하여 최소값을 출력한다.
이전 색깔이 어땠는지에 따라 arr배열에 +1을 해주는지 아닌지 정한다.

1. B로 먼저 색칠하고 필요 부분에 R을 색칠할 경우

• 시작 지점이 R이면 B로 색칠했다가 R로 색칠해야하므로 arr[0] = 2, 아니면 1로 시작한다.
• s[i]가 B면 이전 값을 그대로 가져간다 -> arr[i] = arr[i - 1]
• s[i]가 R이면 이전 문제의 색이 어땠는지에 따라 +1을 해주거나 그대로 가져간다.

2. R로 먼저 색칠하고 필요 부분에 B를 색칠할 경우

• 1번의 반대로 새로운 배열에 값을 저장한다.

3. 둘 중 최소값을 출력한다.

문제 링크

boj/20365

소스코드

PS/20365.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<memory.h>
#include<queue>
using namespace std;

int arr[500001];
int arr2[500001];
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	string s;
	cin >> s;
	arr[0] = 1;
	char pre = s[0];
	if (s[0] == 'R')
		arr[0]++;
	for (int i = 1; i < s.size(); i++)
	{
		if (s[i] == 'B')
			arr[i] = arr[i - 1];
		else if (s[i] == 'R')
		{
			if (s[i] != pre) {
				arr[i] = arr[i - 1] + 1;

			}
			else
				arr[i] = arr[i - 1];
		}
		pre = s[i];
	}
	arr2[0] = 1;
	char pre2 = s[0];
	if (s[0] == 'B')
		arr2[0]++;
	for (int i = 1; i < s.size(); i++)
	{
		if (s[i] == 'R')
			arr2[i] = arr2[i - 1];
		else if (s[i] == 'B')
		{
			if (s[i] != pre2) {
				arr2[i] = arr2[i - 1] + 1;

			}
			else
				arr2[i] = arr2[i - 1];
		}
		pre2 = s[i];
	}
	cout << min(arr[n - 1], arr2[n - 1]);
}