| 시간 제한 | 메모리 제한 |
| 3초 | 256MB |
문제
(원문이 영어라서 gpt에게 번역 하청)
Shagga와 Dolf는 검정색 또는 흰색으로 이루어진 돌로 게임을 하는 것을 좋아합니다. 게임이 시작되면, Dolf는 모든 돌을 왼쪽에서 오른쪽으로 한 줄로 배열합니다. 이제 Shagga의 목표는 모든 검은 돌이 모든 흰 돌의 왼쪽에 오도록 돌들의 순서를 재정렬하는 것입니다. 이를 위해, 그는 서로 다른 색의 돌 두 개를 선택하여 위치를 바꿀 수 있으며, 그 과정에서 Dolf에게 A개의 동전을 지불해야 합니다. 그러나 교환하려는 두 돌이 인접해 있으면, Dolf는 그에게 B개의 동전을 환급해 줍니다. 즉, 그 작업은 Shagga에게 A−B개의 동전만큼 비용이 듭니다.
Shagga는 매우 똑똑하지 않아서, 이 게임을 통해 동전만 잃는다는 것을 아직 깨닫지 못했습니다. 그러나 그는 자신의 한계를 인식하고 있으며, 현재 임의로 돌을 교환하는 방식보다 더 적은 동전을 잃을 수 있는 최적의 방법이 있을 것이라는 것을 알고 있습니다. 그래서 그는 모든 검은 돌이 흰 돌의 왼쪽에 오도록 재배치하기 위해 Dolf에게 지불해야 하는 최소한의 동전 수를 알고 싶어합니다. 당신이 도와주지 않으면 Shagga는 당신을 염소에게 먹일 것이라고 위협하고 있습니다.
입력
첫 번째 줄에는 두 정수 A와 B가 주어집니다. (0 ≤ B < A ≤ 106), 각각 두 돌을 교환하는 비용과 인접한 돌을 교환할 때의 환급 금액을 나타냅니다.
두 번째 줄에는 최대 5000개의 문자로 이루어진 공백이 없는 문자열 S가 주어집니다. 이 문자열의 i번째 문자는 해당 위치의 돌의 색을 나타냅니다. 'B'는 검은 돌을, 'W'는 흰 돌을 나타냅니다.
출력
한 줄에 Shagga가 모든 검은 돌이 흰 돌의 왼쪽에 오도록 돌을 배치하는 데 Dolf에게 지불해야 하는 최소 동전 수를 출력하세요.
풀이
모든 검은 돌이 흰 돌의 왼쪽에 오도록 순서를 재정렬 하라는 말이 좀 애매한데 쉽게 말하면 그냥 검은 돌은 전부 왼쪽으로, 흰 돌은 전부 오른쪽으로 오도록 순서를 바꿔달라는 말이다. 예제 입력 2을 보면 어떤 상황에 비용을 A만큼 써야 하는지 A-B만큼 써야하는지 알 수 있다.
5 3
WBWWBWBWBWBBBWWBBB2번째 칸에 있는 B를 1번째 칸에 있는 W와 바꾸면 2의 비용으로 쉽게 옮길 수 있겠지만 그 오른쪽의 모든 돌들에 대해 2번째 칸이 비게 되고 누군가는 여길 채워야 한다. 맞닿은 돌도 없으니 5의 비용을 들일 수 밖에 없다. 어 그럼 1번째 칸으로 옮기는데 2, 2번째 칸을 채우는데 5가 든다. 만약 1번째와 2번째 칸을 맞바꾸지 않고 멀찍이 있는 검은 돌을 그냥 첫번째 칸으로 옮겼다면 비용 5만으로 채울 수 있다. 그래서 이 문제는 우선 어느 정도 거리까지 A-B 비용으로 옮기는 것이 이득인지 먼저 따져본 후, 그 너머의 거리에 있는 W-B쌍은 모조리 A 비용으로 바꿔주는 것이 답이다. 그리디한 방법으로 해결할 수 있다.
그럼 어떤 돌과 어떤 돌을 옮겨 주는 것이 좋을까? 힌트는 어느 위치에 있는 돌이든 맞닿아있지 않다면 거리와 상관 없이 비용이 A로 고정이라는 데 있다. 가장 멀리 있는 W-B쌍부터 옮겨주면 최대 이익을 얻을 수 있다. 그래서 맨 왼쪽부터 오른쪽으로 탐색하는 i와 맨 오른쪽에서 왼쪽으로 탐색하는 j를 놓고 투 포인터 탐색을 실시하면 된다. i, j 위치에서 W-B쌍이 나타나면 둘의 위치를 거리에 따라 A 비용 또는 A-B 비용으로 바꿔준다. i와 j 사이 거리가 너무 가까워지면 A-B 비용이 나을 수 있다 그 거리는 A // (A - B)로 구할 수 있다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
A, B = map(int, input().split())
B = A - B
limit = A // B
stone = list(input().strip())
i, j = 0, len(stone) - 1
res = 0
while i < j:
while i < len(stone) and stone[i] == 'B': i += 1
while stone[j] == 'W': j -= 1
if i >= j: break
if j - i > limit: res += A
else: res += B * (j - i)
i += 1
j -= 1
print(res)
solution()(편의를 위해 B를 A-B로 바꿨다.)
