[파이썬/python] 행사장 대여(small)

문제

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

---

문제 설명

1. 상현이는 행사장을 대여하려고 한다.
2. 행사장을 완전이 포갤 수 있는 N개의 직사각형을 만든다.
3. N개의 직사각형들은 일부분 혹은 전체가 겹칠 수 있다.
4. 각 직사각형의 좌측 하단, 우측 상단의 좌표를 알려준다.
5. 행사장의 넓이를 구해라.

 

---

풀이

1. X,Y의 최대 크기만큼 배열을 생성하여 0으로 초기화 한다.
2. 각 직사각형 좌표의 값을 +1한다.
3. 전체 배열을 반복문으로 탐색하면서 0이 아닌 위치만 카운트한다.

---

코드

import sys
input = sys.stdin.readline

N = int(input())


board = [[0 for _ in range(500)] for _ in range(500)]
res = 0

for i in range(N):
    x1,y1,x2,y2 = map(int,input().split())
    for j in range(y1,y2):
        for k in range(x1,x2):
            board[j][k]+=1
for row in range(500):
    for col in range(500):
        if board[row][col] > 0:
            res+=1
print(res)

---

시간복잡도

• 최악일 때 $N = 100$ 이며 $x,y$는 최대 $500$이다.
• 각 직사각형의 좌표를 저장할 때 시간복잡도: 약 $O(N*width*height) = O(100*500*500) = O(25*10^6)$
• 넓이를 카운팅할 때 시간복잡도: 약 $O(width*height) = O(25*10^4)$
• 총 시간 복잡도: 약 $O(25(10^4+10^6))$