[c++] 백준 20365: 블로그2

[c++] 백준 20365: 블로그2

🥈실버 3

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

20365번: 블로그2

---

접근

빨간색, 혹은 파란색으로 전체를 칠해놓고, 나머지 색으로 다른 색상이 필요한 부분을 칠해주는 것이 최소의 값이 된다.

문제는 어떤 색으로 전체를 칠할 것이냐였다.

 

두 색중에 더 많은 색이 나타나는 것을 바탕색으로 칠하고, 더 적게 나타나는 색으로 나머지 부분을 칠하는 것이 최소가 될 것이라고 판단했다.

 

1. 입력값에서 R과 B의 개수를 알아낸다.

2. 두 값중 개수가 더 많은 색은 전체 바탕으로 칠해질 색이므로 1을 카운트하고, 거기다가 더 적은 색이 입력값에서 몇 번 나타나는지를 더한다.

 

BBRBRBBR을 예로 들어보면,

B=5, R=3이므로 파란색을 바탕색으로 칠해야 한다. count = 1

B와 R중에 더 적은 수로 나머지 부분을 칠해야 하는데, 이는 곧 R의 개수와 같으므로 count = 1 + 3 = 4가된다.

 

코드

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

int N;
string word;
int R = 0, B = 0;

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

  cin >> N >> word;

  if (word[0] == 'B') B++;  // 첫번째 값을 따로 땐 이유는 word[i-1]에서 index Error가 발생하기 때문이다.
  else R++;

  for (int i = 1; i < N; i++) {
    if (word[i] == 'B' && word[i-1] == 'R') B++;
    if (word[i] == 'R' && word[i-1] == 'B') R++;
  }
  cout << min(R, B) + 1;	// 더 적게 나타나는 색의 개수 + 더 많이 나타나는 색으로 전체를 칠한 수(1)
  return 0;
}