[백준/17615] 볼 모으기 (Python)

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

17615번: 볼 모으기

 

Difficulty : Silver 1

 

Status : Solved

 

Time : 00:14:53

 

 

---

 

문제 설명

 

 

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

 

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

 

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

 

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

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

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

9
RBBBRBRRR

 

출력 예시

 

2

 

 

---

 

풀이

 

각 공을 기준으로 옮기는 경우를 생각하자. 옮긴 후에는 "R...RB..B"꼴 혹은 "B...BR..R"꼴과 같이 같은 색상들이 한 곳으로 모여 있어야 한다.

 

• 첫 단(ball[0]), 혹은 끝 단(ball[-1])에 해당 공이 위치하는 경우 그 공의 위치로 남은 공을 옮기는 게 가장 좋은 선택이다. 이 때 총 공의 개수가 m, 양 끝단에 연속하는 공의 개수가 n이라면 옮기는 횟수는 m-n이 된다.
• 만약 위에 해당하지 않는다면, 모든 공을 한쪽 끝단으로 옮기는 경우밖에 존재하지 않는다. 따라서 옮기는 횟수는 m이 된다.

빨간 공과 파란 공 각각에 그리디하게 이를 적용하면 빠르게 풀이할 수 있다. 

 

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
balls = input().strip()
ball_cnt = {'R' : 0, 'B' : 0}

for ball in balls :
  ball_cnt[ball] += 1

ans = float('inf')
for b in ['R', 'B'] :
  flg = True
  for _balls in [balls, balls[::-1]] :
    if _balls[0] != b :
      continue
    cnt = 1
    flg = False
    for _b in _balls[1:] :
      if _b != b :
        break
      cnt += 1
    ans = min(ans, ball_cnt[b] - cnt)

  if flg :
    ans = min(ans, ball_cnt[b])

print(ans)

풀이 완료!