3653 - 영화 수집

아침에 눈 떴으면 문제 풀어야지 ??

 

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

3653번: 영화 수집

 

오늘의 문제 역시 세그먼트 트리입니다.

 

이 문제에 썰이 있는데, 한 번 풀어보도록 할게요.

---

 

 

때는 S전자에 있었을 때, 회사에서 알고리즘 강의를 들었더랬죠.

 

그리고 해당 강의는 주마다 매번 시험이 있었는데, 총 3문제가 출제됐더랬죠.

 

저는 몇 주간 100점을 놓치지 않았던, 팀 내 에이스 역할을 했더랬죠.

 

그리고, 어느 시험 날 위의 문제가 나오게 됐더랬죠.

 

아마 3시간 시험이었을건데, 시험 종료 20분까지도 위의 문제를 어떻게 풀어야 하는지 몰랐더랬죠.

 

모든 걸 포기하려고 한 순간, 갑자기 아이디어가 떠올랐고, 약 10분만에 위의 문제를 풀고 제출 했더랬죠.

 

결과는 성공, 그 주의 에이스 역할을 지속할 수 있었더랬죠.

 

근데, 그 다음 주부터는 아무리 머리를 써도, 머리가 굴러가지 않고, 게임과 동기와 술 마신다고 바로 나락의 길을 걷기 시작하면서, 모든 이들의 기대를 부쉈더랬죠.

 

아마 제 남은 모든 힘을 저 문제에 썼었던게 아니었나 생각이 드네요.

---

오랜만에 해당 문제를 봐도, 그 때의 아이디어가 떠올라서 쉽게 풀 수 있었습니다.

 

마찬가지로 자기 위의 비디오들의 구간 합을 구하고, 걔를 꺼내고 제일 위에 넣어주고를 반복하면 풀 수 있는 문제입니다.

 

좀 더 친절하게 말 드리자면,

 

1. 원하는 비디오의 위치를 파악한다.

2. 걔 위의 애들 구간합을 구한다.

3. 그 비디오의 위치에 0으로 수정하고,

4. 그 비디오를 제일 최상단(TREE의 제일 위)에 배치한다.

5. 반복

 

import sys

input = sys.stdin.readline


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

    TREE[n] = init(n * 2, s, m, t) + init(n * 2 + 1, m + 1, e, t)
    return TREE[n]


def check(n, s, e, l, r):
    if r < s or s < l:
        return 0
    
    if l <= s and e <= r:
        return TREE[n]
    
    m = (s + e) // 2
    return check(n * 2, s, m, l, r) + check(n * 2 + 1, m + 1, e, l, r)


def update(n, s, e, t, v):
    if t < s or e < t:
        return TREE[n]
    
    if s == e == t:
        TREE[n] = v
        return TREE[n]
    
    m = (s + e) // 2

    TREE[n] = update(n * 2, s, m, t, v) + update(n * 2 + 1, m + 1, e, t, v)
    return TREE[n]
    

T = int(input())
for _ in range(T):
    N, M = list(map(int, input().split()))
    VS = list(map(int, input().split()))

    VIDX = [n + M  for n in range(N + 1)]
    TREE = [0] * (N + M) * 4

    for idx in VIDX[1:]:
        init(1, 1, N + M, idx)

    top = M + 1
    for v in VS:
        print(check(1, 1, N + M, 1, VIDX[v] - 1), end=' ')
        update(1, 1, N + M, VIDX[v], 0)
        top -= 1
        VIDX[v] = top
        update(1, 1, N + M, VIDX[v], 1)
    
    print()

---

이제 진짜 C 꺼내야하나

 

제출할 때마다 무서워 죽겠네

 

오늘도 한 문제 풀었으니,

 

즐거운 하루를 시작해봅시다.

---

이상 3653 - 영화 수집였습니다. ^_^