[백준] 32129 (마법 구슬)

문제 소개

N개의 구역이 일직선으로 놓여 있고, 구슬을 1번 구역에 내려놓으면 현재 가치 > 다음 가치인 동안 오른쪽으로 이동합니다. 멈추면 해당 구역의 가치를 1 높입니다.

아래 시뮬레이터에서 직접 배열을 입력하고 구슬을 굴려보세요.

초기 배열:

Step 0/-1 — 

핵심 관찰: 계단 구조

계단(Stair)이란?

배열을 연속으로 1씩 감소하는 최대 구간들로 분할한 것을 "계단"이라 부릅니다. 구슬은 하나의 계단 내에서는 끝까지 굴러가고, 다음 계단의 시작값이 더 크거나 같으면 거기서 멈춥니다.

[4, 3, 2](시작=4, 길이=3)

[5, 4](시작=5, 길이=2)

계단의 병합

구슬을 계속 넣으면 첫 번째 계단의 시작값이 증가합니다. 이에 따라 최솟값도 올라가고, 최솟값이 다음 계단의 시작값 이상이 되면 두 계단이 하나로 병합됩니다. 병합 후에는 더 큰 하나의 계단이 되어, 이후 구슬이 더 뒤쪽까지 굴러갈 수 있습니다.

계단 병합 과정

계단 1: [4, 3, 2], 계단 2: [5, 4]

1번 구역의 가치를 높여 계단 1의 최솟값을 올린다

자료구조 설계

계단 튜플: `(start, len, deficit, partial)`

(

)

start

계단 시작점(최대)의 가치

len

이어진 계단의 길이

deficit

계단을 완성하기 위해 부족한 구슬의 합

partial

현재 층에 이미 쌓인 구슬 수

예시: 배열 [5, 4, 2]를 하나의 계단으로 표현

시작값 = 5, 길이 = 3, 부족분 = (5-1) - 4 + (5-2) - 2 = 1 (4번째 칸이 3이 아닌 2), 부분 = 0

복잡도 분석

분할 상환 분석

병합은 계단 수를 항상 감소시킵니다. 초기에 최대 N개의 계단이 있으므로, 전체 쿼리에 걸쳐 총 병합 횟수는 O(N)을 넘지 않습니다.

초기

계단 5개

병합 1회

계단 4개

병합 2회

계단 3개

모두 병합

계단 1개

시간 복잡도

각 쿼리에서 while 루프 외의 작업은 O(1)입니다. 병합 루프의 총 실행 횟수는 O(N)이므로, 전체 시간 복잡도는 O(N + Q)입니다.

복잡도 비교

❌ 단순 시뮬레이션

구슬 하나당 최대 O(N) 이동

쿼리당: O(x · N)

O(Q · x · N) ≈ 10¹¹

✅ 계단 자료구조

초기화: O(N)

병합 총합: O(N), 나머지: 쿼리당 O(1)

O(N + Q) ≈ 10⁶

구현

코드 구조

for Vi in V:
    if len(stairs) == 0 or stairs[-1][0] - stairs[-1][1] < Vi:
        stairs.append((Vi, 1, 0, 0))
    else:
        stairs[-1] = (stairs[-1][0], stairs[-1][1] + 1,
            stairs[-1][2] + (stairs[-1][0] - stairs[-1][1] - Vi), 0)

배열을 순회하며 계단 구조를 구성합니다. 현재 값이 마지막 계단의 최솟값보다 엄격히 작으면 기존 계단에 편입시키고, 그렇지 않으면 새 계단을 시작합니다.