[백준] 28018 시간이 겹칠까?(feat.imos법) (python 파이썬)

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

28018번: 시간이 겹칠까?

---

대회에서 해결 못하고 끝나고 해결한 문제. 처음 듣는 알고리즘이어서 신기했다.(누적합 알고리즘 같다)

아직도 모르는게 많은거 같다, 배움에는 끝이 없는 거 같다.

---

아이디어

문제를 보고 시간제한을 고려하지않으면 정말 쉬운 난이도다. 하지만 입력값이 크기 때문에 시간 고민을 해봐야 된다.

 

이 아이디어를 쉽게 말하면, 들어오고 나가는 시간만 저장하면 된다.  

 

먼저 최대 시간(1000000) 크기의 1차원 리스트를 선언하고 값을 0으로 초기화해 준다. 그리고 입장 시간, 퇴장 시간에 맞게 +1을 해준다. 

예제 1 같은 경우 다음과 같다.

in_time = [0, 1, 1, 0, 0,...]

out_time = [0, 0, 0, 1, 1,...]

 

이렇게 리스트 두 개를 만들어주고 DP, 점화식을 세워주면 된다. 

for i in range(1, 1000001):
    D[i] = D[i - 1] + in_time[i] - out_time[i - 1]

문제 조건에서 "각 좌석은 사용이 종료되는 시각에 곧바로 선택될 수 없다."라고 했으니 퇴장시간은 i - 1 시각을 빼준다. 이렇게 하면

D [n]은 n번째 시각에 선택할 수 없는 좌석 수(사람 수라고 생각해도 될 듯)가 된다.

 

아 그리고 똑똑한 분들은 알겠지만 저렇게 리스트 두 개 사용 안 해도 된다. out time값들을  in_time에 -1로 저장하면 된다. 시각에 맞게.

나는 메모리가 넉넉한 거 같아 내 방식으로 작성했다.

---

전체 코드

import sys
N = int(input())

in_time = [0] * 1000001
out_time = [0] * 1000001
D = [0] * 1000001

for _ in range(N):
    a, b = map(int, sys.stdin.readline().split())
    in_time[a] += 1
    out_time[b] += 1

for i in range(1, 1000001):
    D[i] = D[i - 1] + in_time[i] - out_time[i - 1]

Q = int(sys.stdin.readline().rstrip())
Qlist = [int(x) for x in sys.stdin.readline().split()]

for q in Qlist:
    print(D[q])

---

코드 설명

for _ in range(N):
    a, b = map(int, sys.stdin.readline().split())
    in_time[a] += 1
    out_time[b] += 1

앞에서 말한 것처럼 입장, 퇴장 각각 따로 받아준다.

 

for i in range(1, MAXTIME):
    D[i] = D[i - 1] + in_time[i] - out_time[i - 1]

그리고 점화식을 세워준다. 이렇게 (이미 있는 사람 + 입장한 사람들 - 나간 사람들) 간단하게 구현 가능하다.

 

---

지금 보면 간단한 아이디어지만, 테스트 같은 환경에서는 구현하기 쉽지 않다.

오히려 기존에 내가 알고 있는 방법만 고집하는 거 같다. 음... 많은 연습, 체화 그리고 실전 경험이 답인 거 같다.