!https://d2gd6pc034wcta.cloudfront.net/tier/10.svg
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 (추가 시간 없음) | 512 MB | 8619 | 3558 | 2794 | 41.908% |
문제
빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.
- 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
- 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.
예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.
https://upload.acmicpc.net/347db7e2-5704-4a28-ab85-682bf30f3816/-/crop/894x133/0,0/-/preview/
<그림 1>
https://upload.acmicpc.net/347db7e2-5704-4a28-ab85-682bf30f3816/-/crop/894x162/0,228/-/preview/
<그림 2>
https://upload.acmicpc.net/347db7e2-5704-4a28-ab85-682bf30f3816/-/crop/894x166/0,480/-/preview/
<그림 3>
반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.
https://upload.acmicpc.net/cf727ec0-1542-4ca1-bdb8-cfc695a5bdfa/-/preview/
<그림 4>
일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.
입력
첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주어질 수도 있으며, 이 경우 답은 0이 된다.
출력
최소 이동횟수를 출력한다.
서브태스크
번호 배점 제한
1 | 15 | N ≤ 10 |
2 | 22 | N ≤ 1,000 |
3 | 14 | N ≤ 500,000, 처음 상태에서 모든 파란 공은 연속해서 존재한다. |
4 | 49 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
예제 입력 1
9
RBBBRBRRR
예제 출력 1
2
예제 입력 2
8
BBRBBBBR
예제 출력 2
1
알고리즘 분류
문제 풀이
'''
백준 실버1
17615번. 볼 모으기
'''
def min_moves_to_collect_balls(balls):
n = len(balls)
# 왼쪽 끝과 오른쪽 끝에서 연속된 'R'과 'B'의 개수
left_R, left_B = 0, 0
right_R, right_B = 0, 0
# 왼쪽 끝에서 연속된 'R' 세기
for i in range(n):
if balls[i] == 'R':
left_R += 1
else:
break
# 왼쪽 끝에서 연속된 'B' 세기
for i in range(n):
if balls[i] == 'B':
left_B += 1
else:
break
# 오른쪽 끝에서 연속된 'R' 세기
for i in range(n-1, -1, -1):
if balls[i] == 'R':
right_R += 1
else:
break
# 오른쪽 끝에서 연속된 'B' 세기
for i in range(n-1, -1, -1):
if balls[i] == 'B':
right_B += 1
else:
break
# 전체 'R'과 'B'의 개수
total_R = balls.count('R')
total_B = balls.count('B')
# 각 경우의 이동 횟수 계산
moves_left_R = total_R - left_R
moves_left_B = total_B - left_B
moves_right_R = total_R - right_R
moves_right_B = total_B - right_B
# 최소 이동 횟수 반환
return min(moves_left_R, moves_left_B, moves_right_R, moves_right_B)
# 입력 받기
n = int(input().strip())
balls = input().strip()
# 결과 출력
print(min_moves_to_collect_balls(balls))
그냥 그리디로… 나 1년전에 하다 말았던 문제임..왜 기억도 안 나는건데
'코딩테스트 > 백준(Python)' 카테고리의 다른 글
[백준][Python] 12919번. A와 B 2 (골드5) (0) | 2024.07.18 |
---|---|
[백준][Python] 1138번. 한 줄로 서기 (실버2) (0) | 2024.07.18 |
[백준][Python] 14179번. 빗물 (골드5) (0) | 2024.07.17 |
[백준][Python] 14940번. 쉬운 최단거리(실버1) (0) | 2024.07.17 |
[백준][Python]2607번. 비슷한 단어(실버2) (0) | 2024.07.11 |