[BOJ] 1531 투명 - python

TIP

문제 링크 (opens new window)

브루트포스 문제

문제 요약

1. Given:
   • 100x100 크기의 그림
   • N개의 (불투명한) 종이
     • 그림의 현재 부분 위에 M개 이하의 종이가 올려져 있으면, 그림은 그 부분에서 보이게된다.

• 2. Constraints:
  • 0 <= N(종이의 개수) <= 50
  • 0 <= M(threshold) <= 50
  • 1 <= x,y <= 100
• 3. Problem:
  • 보이지 않는 그림의 개수를 구하라
    • 보이지 않을 조건: M 개 이상의 종이가 올려져있을때

문제 접근 및 구현

1. board[i][j] : (i, j) 번째 그림에 올려진 종이의 개수
   • 초기값 : 0
2. put_paper(board, 왼쪽 아래 좌표, 오른쪽 위 좌표)
   • 종이에 가려지는 한 좌표를 (i, j) 라 할때, board[i][j] 값을 1 증가시킨다. (이중 for 문)
3. cnt_of_invisible(board, threshold=M)
   • M 개 이상의 값을 가진 그림의 개수를 구하면 된다. (이중 for 문)
4. 시간 제한 통과하는가? YES. 입력의 크기가 작기때문에
   • (종이의 최대 개수) * (종이의 최대 크기) = 50 * 10000 = 500,000

from sys import stdin
from collections import namedtuple
from typing import List

input = stdin.readline
Point = namedtuple('Point', 'y x')


def cnt_of_invisible(board: List[List[int]], threshold: int):
    def cond(v): return v > threshold
    return sum(cond(val) for row in board for val in row)


def put_paper(board, pos1, pos2):
    # pos1 : left bottom corner
    # pos2 : right top corner
    for y in range(pos1.y, pos2.y + 1):
        for x in range(pos1.x, pos2.x + 1):
            board[y][x] += 1
    return


def main():
    N, M = map(int, input().split())

    # index: 0 ~ 99
    board = [[0 for _ in range(100)] for _ in range(100)]

    for _ in range(N):
        x1, y1, x2, y2 = [int(v) - 1 for v in input().split()]
        put_paper(board, Point(y1, x1), Point(y2, x2))

    print(cnt_of_invisible(board, threshold=M))


main()

TIP

BOJ 제출소스 (opens new window)