[Python 3] BOJ 14595: 동방 프로젝트 (Large)

 

1부터 n번까지 방이 있다.

여기서 반복적으로 'x부터 y번까지의 방'을 벽을 허물어서 한 개의 방으로 만든다.

이후에 총 방의 개수를 세는 문제이다.

 

처음에는 분리 집합으로 Union-Find를 통해 해결하려고 했다.

그러나, 100만개의 방을 5000번 합치게 되면, TLE를 받는다.

 

여기서 앞 방과 뒤 방만 생각하고, 중간에 있는 방들을 생각하지 않아도 되는 방법을 모색했다.

따라서, 검색과 gpt를 통해서 '차분 배열'을 배우게 되었다.

누적 합 (Prefix Sum)의 일종으로서, 시작점과 끝점에 더하고 빼주는 것을 이용하는 알고리즘이다.

 

즉, x번 방과 y번 방 사이의 방은 고려하지 않고,

x번째 방에 1을 더해주고, y번재 방에서 1을 뺀다.

여기서 1을 더해주는 것은 오른쪽 방의 벽을 허물었다는 뜻이고, 1을 빼주는 것은 벽을 허무는 행위를 멈췄다라고 할 수 있다.

왼쪽부터 누적 합으로 더해주면서, 값이 0보다 크면 현재 벽이 허물어져있음을 알 수 있다.

 

예컨데,

[1, 0, 0, -1, 0]이라는 차분 배열이 주어지면, 

1,2,3,4번방이 하나로 이어져 있고, 5번방은 분리되어 있음을 알 수 있다.

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
diff = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    diff[a] += 1
    diff[b] -= 1

removed = 0
current = 0

for i in range(1, n):
    current += diff[i]
    if current > 0:
        removed += 1

print(n - removed)

 

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