Black and White Stones

Black and White Stones

문제 개요

검은 돌과 흰 돌이 섞여 일렬로 놓여 있습니다. 이 게임에서 플레이어는 돌들을 움직여 모든 검은 돌을 왼쪽으로, 모든 흰 돌을 오른쪽으로 모으는 것이 목표입니다. 하지만 돌을 옮길 때마다 코인이 들기 때문에, 최대한 적은 비용으로 목표를 달성해야 합니다. 최소한의 코인 비용으로 돌들을 정렬하는 방법을 찾아보겠습니다.

예시

작은 예로 초기 배치가 BWWB (B는 검은 돌, W는 흰 돌)인 경우를 생각해봅시다.

위치	1	2	3	4
초기	B	W	W	B
목표	B	B	W	W

이 예시에서 A = 2, B = 1이라면 인접 교환은 1코인, 비인접 교환은 2코인이 됩니다.

해결 전략

왼쪽의 흰 돌과 오른쪽의 검은 돌을 서로 교환해야 합니다. 이때 직접 교환할지, 인접 교환을 여러 번 할지를 비용 비교를 통해 결정합니다.

• 직접 교환: A 코인
• 인접 교환: 거리 d면 (A - B) * d 코인

두 방법 중 더 저렴한 쪽을 선택하면 최소 비용으로 정렬이 가능합니다.

코드 분석 (최적화 버전)

def s():
    a, b, t = open(0, 'rb').read().split()
    t = memoryview(t)
    a, b = int(a), int(b)
    b = a - b
    l = a // b
    i, j = 0, len(t) - 1
    r = 0
    while i < j:
        while i < len(t) and t[i] == 66:  # 'B'는 ASCII 66
            i += 1
        while j >= 0 and t[j] == 87:     # 'W'는 ASCII 87
            j -= 1
        if i >= j:
            break
        if j - i > l:
            r += a
        else:
            r += b * (j - i)
        i += 1
        j -= 1
    print(r)

s()

이 버전은 memoryview를 통해 문자열을 바이트 단위로 처리하여 빠르게 동작합니다. 'B'와 'W'는 각각 ASCII 코드 66, 87이므로 숫자로 직접 비교합니다. 주요 전략은 다음과 같습니다:

1. 왼쪽 끝에서 흰 돌(W)을 찾고, 오른쪽 끝에서 검은 돌(B)을 찾는다.
2. 둘의 위치가 교환 대상이면 거리 차를 비교하여 직접 교환 또는 인접 교환 비용 중 최소를 선택한다.
3. 계산한 비용을 누적하고, 인덱스를 한 칸씩 안쪽으로 이동시킨다.

결론

이 최적화 코드는 한 번의 스캔으로 모든 잘못된 흰돌-검은돌 쌍을 처리하면서 최소 비용을 계산합니다. 특히, 돌이 많은 경우에도 빠르게 동작하며 아이디어를 잘 이해하면 구현해볼 수 있습니다.