[백준] 2563. 색종이 python

🐳 링크

백준 2563번 색종이

🐕 문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

그림 출처: https://www.acmicpc.net/problem/2563

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

🐾 풀이 방법

매우 단순하게, 2*2 색종이의 넓이를 계산한다고 생각해보자.
이때, 색종이의 넓이는 2*2 = 4로 계산할 수도 있고, 색종이를 모두 1*1짜리 칸으로 나누어 각각의 넓이인 1+1+1+1 = 4 로 계산할 수 있다. 코드로 구현할 때엔 아래 방법을 이용할 것이다.

paper라는 101*101 배열을 선언하고, 색종이의 왼쪽 하단 포인트의 위치가 주어지면 그 포인트로부터 x+10, y+10 (색종이의 길이가 10이므로)만큼을 1로 채운다. 이후 paper에서 1인 곳의 합을 구하면, 겹친 부분도 문제 없이 전체 색종이의 넓이가 계산된다.

모든 테스트케이스 성공 코드

paper = [[0] * 101 for _ in range(101)]
n = int(input())
area = 0
for i in range(n):
    x, y = map(int, input().split())
    for j in range(y, y+10):
        for k in range(x, x+10):
            paper[j][k] = 1


for row in paper:
    if 1 in row:
        area += sum(row)

print(area)