[python] 17165, 볼 모으기 : 그리디

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

17615번: 볼 모으기

 

[문제]

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

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

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

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

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

 

[입력]

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

 

[출력]

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

 

[예제]

 

[풀이]

💡 문제 요약 : 규칙에 따라 볼을 이동하여 같은 색끼리 모으는 최소 이동횟수 구하기

💡 풀이 포인트

 문제 그대로 풀면 안되고, 아이디어를 이용해서 풀어야 하는 문제인 것 같다. 아직 이렇게 아이디어를 요하는 문제는 조금 어렵다 .. 아니 사실 많이 🥲

 

먼저 내 코드는 ... 시간 초과 코드 ... 로 15점에서 멈췄다 ...

n = int(input())
sen = input()

def ball(word):
  answer = []
  cnt = 0
  for i in range(n):
    if sen[i] == word:
      cnt += 1
    else:
      if cnt != 0:
        answer.append(cnt)
        cnt = 0
  answer.append(cnt)
  if answer[0] > answer[-1]:
    return sum(answer[1:])
  else:
    return sum(answer[:-1])

if sen[0] == sen[-1]:
  if sen[0] == 'R':
    alpha = 'B'
  else: alpha = 'R'
  print(min(ball(sen[0]), sen.count(alpha)))
else:
  print(min(ball('B'), ball('R')))

 

그래서 확인한 정답 코드는 바로 요거였다 !

매우 심플하게 푸셨는데 방법은 왼쪽 혹은 오른쪽으로 각 색깔별로 모은다고 경우의 수를 두고 각각 모두 구해보는 것이다. 구해보고 그 중 최솟값을 반환하는 방법이다. 진짜 너무 간단해서 ... 허탈했다 머리만 잘 돌렸다면 풀 수 있는 문제였다 ...

import sys

N = int(sys.stdin.readline().strip())
balls = str(sys.stdin.readline().strip())
cnt = []

# 우측으로 레드 모으기
rexplore = balls.rstrip('R')
cnt.append(rexplore.count('R'))

# 우측으로 블루 모으기
rexplore = balls.rstrip('B')
cnt.append(rexplore.count('B'))

# 좌측으로 레드 모으기
lexplore = balls.lstrip('R')
cnt.append(lexplore.count('R'))

# 좌측으로 블루 모으기
lexplore = balls.lstrip('B')
cnt.append(lexplore.count('B'))

print(min(cnt))