[백준] 28108-시간이겹칠까?

문제바로가기

처음에는 그냥 시작부터 끝까지의 수를 순회해서 값을 저장해둔다음 그 값을 출력하면 끝나는 문제라고 생각했다.

import sys
sys.setrecursionlimit(10**6)

N = int(sys.stdin.readline())
use = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
time = dict()
for i in use:
    for t in range(i[0], i[1]+1):
        if t not in time:
            time[t] = 1
        else:
            time[t] += 1

Q = int(sys.stdin.readline())
check = list(map(int, sys.stdin.readline().split()))
for i in check:
    if i not in time:
        print(0)
    else:
        print(time[i])

하지만 해당 방식의 위 코드는 시간초과가 난다. range(i[0], i[1]+1)부분이 i가 클수록 (예를들어 1과 1000000이면) 부담되기 떄문에 그렇다. 따라서 이 문제도 누적합을 이용해야한다.

# 누적합 방식으로 풀어보기
import sys
sys.setrecursionlimit(10**6)


N = int(sys.stdin.readline())

MAX_T = 1_000_002  
diff = [0] * MAX_T

for _ in range(N):
    s, e = map(int, sys.stdin.readline().split())
    diff[s] += 1
    diff[e+1] -= 1 

for i in range(len(diff)-1):
    diff[i+1] += diff[i]
    
Q = int(sys.stdin.readline())
check = list(map(int, sys.stdin.readline().split()))
for i in check:
    print(diff[i])

종료까지 1이란 플레그가 있어야 하는데 누적합으로 그걸 어떻게 아냐고요?
바로 종료 다음 시점을 -1을 넣으면 된다. 그럼 종료까지는 diff가 누적해서 합을 구하게 되지만 그 이상은 안된다는거~
간단한 플래그로 완성할 수 있다.