2243 - 사탕상자

최근 골드 문제만 풀다가, 도저히 레벨이 안올라서, 한 번 플레 문제 오랜만에 도전해보겠습니답.

trick or treat !!

할로윈이기도 하니, 사탕 문제 한 번 풀어보겠습니답.

 

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

2243번: 사탕상자

 

문제는 당연 세그먼트 트리(경험치 맛 집)

 

처음에 이 문제 보고 아이디어 도달하기엔 좀 오랜 시간이 걸렸는데,

 

사탕의 맛을 1 ~ 1000000까지 굳이 정한 이유가 있을까,,, 하다가

 

아항 얘들이 리프 노드겠구나, 밸류는 갯수겠네라고 생각하니 세그먼트 트리가 그려지더군요.

 

그렇게 풀어봤습니다.

 

import sys

input = sys.stdin.readline

def init(n, s, e, t, v):
    if t < s or e < t:
        return tree[n]
    
    if s == t == e:
        tree[n] += v
        arr[n] = t
        return tree[n]
    
    m = (s + e) // 2
    tree[n] = init(n * 2, s, m, t, v) + init(n * 2 + 1, m + 1, e, t, v)

    return tree[n]

def get(n, s, e, g):
    if (s == e):
        tree[n] -= 1
        print(arr[n])
        return tree[n]

    l = tree[n * 2]
    m = (s + e) // 2
    if l >= g:
        get(n * 2, s, m, g)
    else:
        get(n * 2 + 1, m + 1, e, g - tree[n * 2])

    tree[n] = tree[n * 2] + tree[n * 2 + 1]

    return tree[n]

N = int(input())
tree = [0] * (1000000 * 4)
arr = [0] * (1000000 * 4)

for _ in range(N):
    cmd = list(map(int, input().split()))
    if cmd[0] == 1:
        get(1, 1, 1000000, cmd[1])
    elif cmd[0] == 2:
        init(1, 1, 1000000, cmd[1], cmd[2])

 

이 문제를 풀면서 신경써야하는 부분이 2가지가 있었는데요.

 

첫 번째로는 리프노드에 도달 했을 시, "해당 노드가 책임지는 사탕의 맛이 무엇인가" 였는데, 이건 따로 index를 담는 arr를 만들어서 해결했고,

 

두 번째가 이 문제의 핵심으로, 과연 현재 내가 찾으려는 등수의 사탕이 현재 노드 기준 왼쪽에 있나 오른쪽에 있나가 핵심인데, 이는 왼쪽노드가 찾으려는 값보다 작거나 크면 ? 왼쪽에 사탕을 찾으면 되고, 아니면 오른쪽에서 찾으면 됩니다.

 

이 말이 무슨 말이냐 ?

 

요걸 한 번 상상해봅시다.

 

여기서 제가 5번째로 맛있는 사탕을 찾고 싶다고 했을 때, 1번 노드에서 왼쪽의 갯수는 4이고, 오른쪽은 3이죠 ?

 

즉, 5번째는 오른쪽에 있다는 뜻입니다.

 

그러고 오른쪽 노드로 넘어가는데, 여기서 문제, 찾고자 하는 5번째의 값은 오른쪽으로 넘어갔을 때, 무슨 값이 되어야 할까요.

 

바로 오른쪽 서브 트리에서 첫번째로 맛있는 사탕을 찾아야 합니다.

 

그래서 g - tree[n * 2]를 해줬더랬죠.

 

이 두 가지만 이해가 되신다면, 쉽게 문제를 해결하실 수 있으셨을 거 같네요. 

---

이상 2243 - 사탕상자였습니다. ^_^