2243 사탕상자 python

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

2243번: 사탕상자

 

 

 

문제 접근

세그먼트 트리로 구현했다.

구간 합에서 개수를 파악하고 좌측과 우측중 어디로 이동할지 판별하면 된다.

현재 노드에서 자식노드중 좌측의 크기보다 현재 접근하려는 개수가 더많으면 우측으로 이동하면 된다.

 

 

시간 메모리도 잘나왔고 1트에 코드도 엄청 짧게나와서 만족스럽다

 

 

 

코드

import sys
import math

input = sys.stdin.readline
"""
2243

"""

def getOut(count, index):
  while index<node:
    index*=2
    if tree[index]<count:
      count -= tree[index]    
      index += 1
  print(index-node)
  update(index-node, -1)


def update(target, val):
  index = node + target
  tree[index] += val
  while index>1:
    index //= 2
    tree[index] = tree[index*2] + tree[index*2+1]
  

n = int(input())
node = 2** math.ceil(math.log2(1000000))
tree = [0] * (node*2+1)

for _ in range(n):
  ABC = list(map(int,input().split()))
  if ABC[0] == 1:
    getOut(ABC[1], 1)
  else:
    update(ABC[1],ABC[2])