ChangMinYang

코딩노잼

[Silver I] 볼 모으기 - 17615

문제 링크

성능 요약

메모리: 31452 KB, 시간: 52 ms

분류

그리디 알고리즘(greedy)

문제 설명

빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.

  1. 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
  2. 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.

예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.

<그림 1>

<그림 2>

<그림 3>

반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.

<그림 4>

일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.

입력

첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주어질 수도 있으며, 이 경우 답은 0이 된다.

출력

최소 이동횟수를 출력한다.

풀이

  • 레드와 블루를 오른쪽 왼쪽으로 모으는 가능한 모든 경우인 4가지 경우를 생각한다.
  • 하나의 색상과 방향을 정해 끝 방향에 연속으로 몰려있다면 제거하고 남은 볼의 개수를 카운트한다.
  • 결국 나머지 공들은 모두 1번씩 이동하게 된다는 것을 알았다면 쉽게 풀렸을 문제였다.
  • 처음에는 어떠한 공을 기준을 잡고 할까 싶어 가장 개수가 적은 공을 기준으로 풀면 되겠다고 생각하고 풀었다.
  • 가장 작은 개수의 볼을 뭉쳐있다면 전부 오른쪽과 왼쪽으로 이동하여 카운트를 하려 했다.
  • 개수가 같은 경우가 있다면 모든 색의 이동을 카운트하려다 꼬이기 시작하였고,, 결국 시간이 너무 지나 답지를 확인했다.
  • 시간을 좀 더 들였거나 차분하게 그리면서? 풀었다면 금방 풀었을 수도 있겠지만 결국 빠르게 풀리지 않았다 ㅠㅠ 그리디 쉬운 듯 어려운 듯..하아😑

댓글남기기

참고