백준 20365번 블로그2 (C++)

백준 20365번

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

20365번: 블로그2

 

 

문제설명

숫자 N을 받고 R,B를 입력받는다

해야할일을 해결한경우 B(파란색) 아닌경우 R(빨간색)으로 페인트로 칠할 때 최소의 값

BBRBRBBR일 때  파란색으로 모두 칠하고 빨간색을 3번 칠하면 총 4번으로 해결가능

 

 

접근

1. 페인트로 한번에 칠하기 때문에 연속된 색깔을 하나로 줄여서 배열에 입력 (한번에 칠하기 때문에 BBR, BR같음)

ex) BBRBBR 일때 BRBR

2. 연속된 색깔을 줄이고 R,B의 개수를 카운팅

3. 더많은 색깔의 수를 베이스로 하여 1번 + 나머지 색깔을 칠한 수 

ex) BRRBBRB -> BRBRB -> B=3,R=2 B가 더 큰값이니 B로 덮은후 R을 2번 더해줌 -> 1+2 -> 결과:3

 

 

코드

#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>

using namespace std;



char arr[500001] = { 0, };

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


	int R = 0, B = 0;
	int N;
	cin >> N;

	int sum = 0;
	int size = 0;

	char tmp;
	for (int i = 0,pt=0; i < N; i++)
	{
		cin >> tmp;

		if (i == 0)
		{
			arr[pt] = tmp; 
			size++; 
			pt++;
		}
		else if (i != 0 && arr[pt - 1] != tmp)
		{
			arr[pt] = tmp; 
			size++; 
			pt++;
		}
	}
	

	
	for (int i = 0; i < size-1; i++)
	{
		if (arr[i] == 'R')
			R++;
		else if (arr[i] == 'B')
			B++;
	}
	if (R < B)
		sum += 1 + B;
	else
		sum += 1 + R;

	cout << sum;
	

	return 0;

}

 

풀이

1. 우선 500001 크기의 배열을 만들고 초기화

2. i값과 동시에 pt(배열위치) 선언후 배열에 R,B값이 들어가면 pt를 증가

3. 마지막에 비교후 계산