백준 3572 - Billboard (Python)

문제 정보

• https://www.acmicpc.net/problem/3572
• 세그먼트 트리

---

문제 정리

크기가 $H \times W$인 게시판이 있고, 여기에 크기가 $1 \times w_i$ 인 직사각형 모양의 공지사항을 $N$개 붙이려고 한다. 공지사항을 붙일 때는 아래와 같은 규칙을 따라야 한다.

• 공지사항을 놓을 수 있는 위치 중 가장 위쪽에 선택.
• 그런 위치가 여러 개라면, 그 중 가장 왼쪽 위치를 선택.
• 공지사항을 붙일 수 있는 공간이 없다면 붙이지 않음.

위 조건을 만족하면서 각 공지사항들이 몇 번째 행에 붙는지 구하는 문제이다.

---

풀이

• 나이브한 풀이부터 생각해보자.
  [0, H]의 구간을 탐색하면서 남은 공간이 $w_i$보다 큰 행의 첫 번째 위치를 찾는 쿼리를 $N$번 처리해야 한다.
  이 경우, $O(NH)$의 시간이 걸리게 된다. $N \leq 200,000$이고, $H \leq 10^9$이기 때문에 TLE가 발생한다.

• 여기서 한 가지 관찰로 $H$의 값을 줄일 수 있다.
  공지사항의 개수는 최대 $200,000$이고, 각 행에 하나씩만 들어간다 쳐도 $H$는 최대 $200,000$까지만 차게 된다.
  즉, $H \leq 200,000$라고 봐도 된다.

• 그렇지만 여전히 $200,000 \times 200,000$이라 TLE가 발생한다. 시간을 어디서 줄일 수 있을까?
  우리가 찾고자 하는 값은 남은 공간 중 $w_i$보다 큰 행의 첫 번째 값이다.
  세그먼트 트리에 (현재 행 구간에서 남은 공간의 최대값)을 저장한다면 하나의 공지사항을 추가할 때 $O(logH)$의 시간만 걸리게 된다.

• 총 O(NlogN)의 시간에 모든 쿼리를 처리할 수 있게 된다.

---

후기

H값을 안줄이고 그냥 넣었다가 MLE를 받았다.

---

코드

# 백준 3572

import io
from array import array

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


# 크기가 N인 세그먼트 트리 빌드 및 [0, index]번까지만 value로 채우기
def build(N, index, value):
    tree = array('i', [0]) * (N*2)
    for i in range(index):
        tree[N+i] = value

    for index in range(N-1, 0, -1):
        tree[index] = max(tree[index<<1], tree[index<<1 | 1])

    return tree


# index번째 값을 value만큼 감소
def update(N, tree, index, value):
    # index += N
    tree[index] -= value

    while index > 1:
        index >>= 1
        tree[index] = max(tree[index<<1], tree[index<<1 | 1])


# tree에 value 길이를 넣을 수 있는 최초 인덱스 반환
def query(N, tree, value):
    index = 1

    while index < N:
        left = index<<1
        right = left | 1

        if tree[left] >= value:
            index = left
        elif tree[right] >= value:
            index = right
        else:
            return -1

    return index


def main():
    Y, X, Q = map(int, input().split())
    Y = min(Y, Q)
    size = 1<<Y.bit_length()
    tree = build(size, Y, X)

    for _ in range(Q):
        value = int(input())

        # 알림판을 추가할 수 있는 최초 위치 찾기
        pos = query(size, tree, value)

        # 알림판 추가 연산
        if pos != -1:
            update(size, tree, pos, value)
            print(pos-size+1)
        else:
            print(-1)


main()