2 minute read

문제 링크

https://www.acmicpc.net/problem/31431

풀이

각 블록을 정점으로 생각하면 입력이 ETT 방문 순서와 유사하다는 것을 알 수 있다.

스택에 넣었다 뺐다 하면서 각 코드 블록의 크기와 ETT 번호를 매겨준 뒤 세그먼트 트리에서 관리해주면 된다.

여기서 주의할 점은

for i in range(N):
    for j in range(N):
        for k in range(N):
            s += 1

이런 식의 코드는 파싱하기 까다로울 수 있는데, 헤더가 들어올 때마다 더미 심플문을 껴주면 쉽게 처리할 수 있다.

마지막 입력의 인덴트 레벨이 1 이상일 경우 아직 빠져나오지 않은 블록을 처리해주는 것도 잊지 말자.

세그먼트 트리는 블록의 크기로 초기화하고, 각 블록이 포함하는 구간의 합을 구했을 때 아직 접히지 않은 부분의 크기가 나오도록 하면 된다..

이때 어떤 쿼리에서 코드를 접었다면 지금 입력이 들어온 정점만 수정해도 구간 합은 멀쩡하다. 어차피 다음에 들어오는 쿼리는 이번에 변경한 구간을 전부 포함하거나 / 아예 포함하지 않기 때문이다. (현재 보이는 줄만 접거나 펼 수 있음)

접힌 코드를 다시 펼 때는 정점의 값을 원래 블록 크기로 만들어주면 안쪽의 접힌 상태 그대로 복구할 수 있다.

코드

import sys
from math import ceil, log
input = sys.stdin.readline

N, Q = map(int, input().split())


block = [(-1, 0)]


cnt = 0
st = [(-1, 0, 0)] # 띄쓰, 타입, in
visible = N
for _ in range(N):
    l, t = input().split()
    l = int(l)
    t = 1 if t == 'h' else 0
    if l == 0 and t == 0:
        continue
    while l < st[-1][0]:
        size = 0
        while not st[-1][1]:
            size += 1
            st.pop()
        block[st[-1][2]] = (cnt, size)
        st.pop()
    if t:
        cnt += 1
        block.append((0, 0))
    st.append((l, t, cnt))
    if t:  # 더미 심플문
        st.append((l+1, 0, cnt))
while st and 0 < st[-1][0]:
    size = 0
    while not st[-1][1]:
        size += 1
        st.pop()
    block[st[-1][2]] = (cnt, size)
    st.pop()

B = len(block)
H = ceil(log(B, 2))
treeSize = pow(2, H+1)
tree = [0]*(treeSize+1)
startIndex = treeSize // 2
for i in range(B):
    tree[startIndex+i] = block[i][1]

for i in range(startIndex+B, 0, -1):
    tree[i//2] += tree[i]



def editTree(i, new):
    while i != 0:
        tree[i] += new
        i //= 2


def getSum(start, end):
    res = 0
    while start <= end:
        if start % 2 == 1:
            res += tree[start]
            start += 1
        if end % 2 == 0:
            res += tree[end]
            end -= 1
        start, end = start//2, end//2
    return res


isFold = [0]*B
for _ in range(Q):
    cmd, *x = input().split()
    if cmd == 'p':
        print(visible)

    else:
        b = int(x[0])
        if not isFold[b]:
            rest = getSum(startIndex+b, startIndex+block[b][0])
            visible += -rest + 1
            editTree(startIndex+b, -rest+1)
            isFold[b] = 1

        else:
            visible += block[b][1] - tree[startIndex + b]
            editTree(startIndex + b, block[b][1]-tree[startIndex+b])
            isFold[b] = 0


리뷰

개인적으로 비재귀 세그먼트 트리를 더 선호하기 때문에 이번에도 반복문으로 풀어주었다.

처음에는 더미 심플문 없이 풀었다가 WA를 받았는데, 다른 블록의 헤더만 포함하는 블록을 생각하지 못했다.

사실 틀린 이유는 블록을 끝내는 기준이 모호해서 그렇다. 이전 줄이 헤더냐 심플문이냐를 따지면서 하면 더미 없이도 풀 수 있을 것 같긴 하다. 더미를 쓰면 머리가 덜 복잡해질 뿐…

마침

SUAPC Winter 대회가 얼마 남지 않아서 작년 대회의 연습 세션 문제를 풀어보았다.

파이썬 사용자라면 그냥 지나치기 힘든 제목이다. 파이썬 문제는 파이썬으로 풀어줘야 우주의 균형에 기여할 수 있다.

최근에는 솔브드 플래티넘 1을 달성했는데 실력이 그만큼 늘었는지는…… 글쎄?

어쨌든 대회에서 좋은 성적을 거둘 수 있었으면 좋겠다.

Leave a comment