[파이썬/python] 백준 - 5625 페스트리

문제

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

---

문제 설명

1. 삼각 패스트리 N개의 각 x1,y1, x2,y2, x3,y3 좌표가 주어진다.
2. 총 M번의 칼질을 진행할 때, 총 몇 개의 페스츄리가 잘리는지 구해야 한다.
   1. 칼질은 수평, 수직 방향으로만 가능하다.
   2. 칼질은 음이 아닌 정수의 좌표에서만 가능하다.
   3. 모든 칼질은 독립적이기 때문에 한번 칼질을 하면 페스츄리는 다시 원래 모양으로 돌아온다.

 

---

풀이

매번 칼질을 할 때마다 각 페스츄리가 잘리는 범위인지 판단하는 문제이다.

 

최초의 접근은 각각의 칼질을 할 때 모든 페스츄리 범위에 대해 검사하여 몇 개가 잘리는지 확인하는 방식이었다.

 

칼질을 총 M회 진행되며 각 칼질마다 N개의 좌표를 검사해야 한다.

즉 M*N 만큼의 연산이 필요하기 때문에 $N = 10^5, M = 10^5$, 약 $10^10$의 연산이 필요하다.

 

시간 제한은 1초이기 때문에, 시간초과가 발생한다.

 

즉,  N*2 아래의 시간복잡도로 문제를 해결해야 하기 때문에 다른 방법을 생각해야 했다.

 

사실 이 문제를 풀 방법에 대해서 따로 찾아내지 못했고, 새로운 기법에 대해 알게 되었다.

차분 배열이라는 기법이다.

 

차분 배열은 보통 누적합과 함께 사용되며, 연속된 범위 구간에 대해서 O(N)만으로 데이터를 업데이트가 가능한 기법이다.

 

1번 예제를 통해 이해해보자.

3
1 0 0 2 2 2
1 3 3 5 4 0
5 4 4 5 4 4
4
x = 4
x = 1
y = 3
y = 1

 

3개의 페스츄리에 대해 x와 y의 최소 최대 범위를 구하면 아래와 같다.

페스츄리	X(min,max)	Y (min,max)	X 잘리는 구간	Y 잘리는 구간
1	(1,2)	(0,2)	X	1
2	(1,4)	(0,5)	2,3	1,2,3,4
3	(4,5)	(4,5)	X	X

 

범위의 끝 부분에서 칼질을 해도 페스츄리는 잘리지 않는다. 따라서 양 끝을 제외한 범위가 페스츄리가 잘리는 구간이라고 볼 수 있다.

 

2번 페스츄리에서 X는 2,3일 때 잘리게 되며, 4일 때 자를수 없게 된다.

Y또한 1,2,3,4일 때 잘리게 되고, 5일 때 자를 수 없게 된다.

 

우리는 연속되는 범위에서 잘리는 페스츄리의 개수를 구하기 싶기 때문에, 전체를 다 탐색하게 되면 $O(N^2)$만큼의 연산이 필요하다.

 

하지만 시작지점(+1)과 끝나는 지점(-1)만 기록하고 마지막에 연속된 합을 구한다면 $O(N)$만큼의 연산으로 모든 개수를 구할 수 있다.

 

Y에 대해서 확인해보자.

 

시작범위는 +1, 종료범위는 -1을 연산한다.

이 때 x,y가 1만큼 차이나면 어떻게 해도 자르지 못하기 때문에 배열에 갱신하지 않아도 된다.

 

1번 페스츄리

시작범위 : 1, 종료범위 : 2

0	1	2	3	4	5	6
0	1	-1	0	0	0	0

 

2번 페스츄리

시작범위 : 1, 종료범위 : 5

0	1	2	3	4	5	6
0	2	-1	0	0	-1	0

 

3번 페스츄리

갱신 필요 없음

0	1	2	3	4	5	6
0	2	-1	0	0	-1	0

 

 

최종 배열에서 순차적으로 누적합(페스츄리의 개수)을 구하면 다음과 같다.

0	1	2	3	4	5	6
0	2	1	1	1	0	0

 

이 문제는 누적합 + 차분배열 기법을 통해서 문제를 풀이할 수 있었다.

 

솔직히 연속된 좌표로 주어지는 문제는 굉장히 많았는데 보통 이분탐색이나 해시 구조로 풀리는 경우가 많아서 이분탐색이라는 고정관념을 좀 가지고 생각하다가 시간을 많이 썼다.

 

차분 배열은 처음보는 기법인데 기존에 알았다면 더 쉽게 풀었을 문제들이 많았을 것 같았다. 이번 기회에 정리하고 잊지 않도록 해야겠다.

---

코드

import sys
input = sys.stdin.readline

N = int(input())
MAX_SIZE = int(1e6)+1

x = [0 for _ in range(MAX_SIZE)]
y = [0 for _ in range(MAX_SIZE)]

for i in range(N):
    x1,y1,x2,y2,x3,y3 = map(int,input().split())
    sx,ex = min(x1,x2,x3), max(x1,x2,x3)
    sy,ey = min(y1,y2,y3), max(y1,y2,y3)

    if ex-sx > 1:
        x[sx+1] += 1
        x[ex] -= 1
    
    if ey-sy > 1:
        y[sy+1] += 1
        y[ey] -= 1

for i in range(1, MAX_SIZE):
    x[i] = x[i-1]+x[i]
    y[i] = y[i-1]+y[i]

M = int(input())

for i in range(M):
    q = input().strip().split(' ')
    num = int(q[2])
    
    if q[0] == 'x':
        print(x[num])
    elif q[0] == 'y':
        print(y[num])

---

시간복잡도

• 상수를 제외하고 $O(N)$만큼의 시간복잡도가 소요된다.