[백준] 17615. 볼 모으기 <C++>

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

17615번: 볼 모으기

음.. 무언가 규칙이 있을 것 같기는 한데 떠오르지는 않았다...

 

그래서 정말 단순하게 알고리즘을 생각했다.

 

파란색들을 왼쪽으로 다 모을 때, 오른쪽으로 모을 때

 

빨간색들을 왼쪽으로 다 모을 때, 오른쪽으로 모을 때

 

(코드에서 정말로 배열의 각 방을 스왑하거나 하지는 않는다. 개수를 셀 뿐이다.)

 

이렇게 네 가지의 경우를 모두 구해 최소값을 구하도록 만들었다.

 

 

 

RBBBRR

 

빨간 색을 왼쪽으로 모으는 경우를 생각해보자.

 

 

0번 방에 빨간색이 있다. 개수를 세주지 않는다. (아직 파란색이 나오지 않았기 때문)

 

1번 방에 파란색이 있다. 개수를 세주지 않는다. (파란색이기 때문)

 

2번 방에 파란색이 있다. 개수를 세주지 않는다. (파란색이기 때문)

 

3번 방에 파란색이 있다. 개수를 세주지 않는다. (파란색이기 때문)

 

4번 방에 빨간색이 있다. 개수를 세준다. (빨간 색이고, 파란색이 중간에 끼어있기 때문이다.)

 

5번 방에 빨간색이 있다. 개수를 세준다. (빨간 색이고, 파란색이 중간에 끼어있기 때문이다.)

 

= 2가 나온다.

 

 

 

 

RBBBRR

 

빨간 색을 오른쪽으로 모으는 경우를 생각해보자.

 

5번 방에 빨간색이 있다. 개수를 세주지 않는다. (아직 파란색이 나오지 않았기 때문)

 

4번 방에 빨간색이 있다. 개수를 세주지 않는다. (아직 파란색이 나오지 않았기 때문)

 

3번 방에 파란색이 있다. 개수를 세주지 않는다. (파란색이기 때문)

 

2번 방에 파란색이 있다. 개수를 세주지 않는다. (파란색이기 때문)

 

1번 방에 파란색이 있다. 개수를 세주지 않는다. (파란색이기 때문)

 

0번 방에 빨간 색이 있다. 개수를 세준다. (빨간 색이고, 파란색이 나온 적이 있기 때문이다.)

 

= 1이 나온다. 

 

아까 나왔던 2보다 1이 더 작기 때문에 1을 기억한다.

 

 

이처럼 파란색도 마저 해준다면 결국엔 1이 출력된다.

 

 

이 과정을 구현한 코드이다.

 

 

 

#include <iostream>
using namespace std;

char arr[500001];
int n, cnt, sw, m=500001;  //n=볼의 개수, m=최소값
int i, j;  //반복문에서 사용할 변수

void set(){
  sw=0;					
  m= cnt<m ? cnt : m;
  cnt=0;
}

int main() {
  cin>>n;
  cin>>arr;

  for(i=0; i<n; i++)		//빨간색을 왼쪽으로 모을 경우 
  {
    if(arr[i]=='B') sw=1;		//파란색이 나오는지 체크한다.
    if(sw && arr[i]=='R') cnt++;	//파란색이 나왔었는지 확인하고, 빨간색인지 확인하여 개수를 세준다.
  }set();				//다음 반복문을 위해 사용한 변수를 초기화를 해주고, 최소값을 구한다.
  for(i=n-1; i>=0; i--)		//빨간색을 오른쪽으로 모을 경우
  {
    if(arr[i]=='B') sw=1;
    if(sw && arr[i]=='R') cnt++;
  }set();

  for(i=0; i<n; i++)		//파란색을 왼쪽으로 모을 경우
  {
    if(arr[i]=='R') sw=1;
    if(sw && arr[i]=='B') cnt++; 
  }set();
  for(i=n-1; i>=0; i--)		//파란색을 오른쪽으로 모을 경우
  {
    if(arr[i]=='R') sw=1;
    if(sw && arr[i]=='B') cnt++;
  }set();

  cout<<m;
}