BOJ 1531 - 투명

문제

BOJ 1531 - 투명

100×100 크기의 그림 위에 N장의 불투명한 직사각형 종이를 올린다. 한 칸에 M장까지는 투명하게 보이지만, M장을 초과하면 그림이 가려진다. 가려지는 칸의 수를 구하라.

입력

첫째 줄에 N과 M, 이후 N줄에 각 종이의 좌상단 (x1, y1)과 우하단 (x2, y2) 좌표가 주어진다.

출력

그림이 보이지 않는 칸의 수를 출력한다.

예제

풀이

100×100 배열에 각 종이가 덮는 영역을 1씩 누적하고, M 초과인 칸을 세면 된다.

1. 100×100 크기의 2차원 배열을 0으로 초기화한다
2. 각 종이에 대해 (x1, y1)부터 (x2, y2)까지 모든 칸에 1을 더한다
3. 전체 배열을 순회하며 값이 M을 초과하는 칸의 수를 센다

핵심 아이디어: 격자 크기가 100×100으로 고정이므로 단순 누적으로 충분하다.

코드

N, M = map(int, input().split())
li = [[0]*100 for _ in range(100)]
for _ in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            li[i-1][j-1] += 1
cnt = 0
for i in range(100):
    for j in range(100):
        if li[i][j] > M:
            cnt += 1
print(cnt)

복잡도

• 시간: O(N × 면적 + 10000)
• 공간: O(10000)