[Python] 백준 2563번 색종이

1. 문제이해

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

 

가로, 세로의 크기가 각각 100인 정사각형 모양의 도화지가 존재한다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 것이 목표이다.

 

 

2. 문제 풀이

 

실버 5의 단순 구현 문제이다.

 

문제를 처음 접근하면서, 단순히 색종이를 하나씩 붙인다는 생각으로 접근하면 매우 복잡한 문제가 되어버린다.

하나씩 종이를 붙여가면서 겹치는 영역을 빼줄 생각을 하면 어렵다는 거다.

몇개의 색종이를 붙일지도, 몇개의 색종이가 겹칠지도, 겹치는 영역이 몇개일지도 정해진 것이 없다.

예를 들어, 10개의 종이를 붙인다 했을때, 10개의 겹치는 영역이 생긴다고 하면 다 빼주고 9번 더해줄것인가?

그렇게 되면 문제가 너무 복잡해진다는거다.

 

정해진 것, 주어진 것 위주로 생각하자.

우리에게 주어진 것은 전체 종이가 가로, 세로의 크기가 각각 100인 정사각형 모양의 도화지이며,

가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 계속해서 붙여간다는거다.

 

그렇다면 반대로 생각해보자. 붙이는게 아니고 빼주는거다.

전체 100x100 크기의 도화지에서, 10x10 크기의 종이들에 해당하는 영역을 오려내준다고 생각하면 문제가 편해진다.

한번 오려낸 영역에 대해서는 다시 겹치는 것을 생각해 줄 필요가 없다.

 

이를 코드로 구현해보면, 전체 100x100 크기의 도화지를 100x100 크기의 행렬로 두고,

N개의 색종이의 각 시작 좌표 (x, y)에 대해 1 0x10 크기의 종이들에 해당하는 영역에 대해 값을 빼주면 된다.

자세한 코드는 아래와 같다.

 

 

3. 소스코드

paper = []  # 전체 도화지
for i in range(100):
    paper.append([-1]*100)  # -1값으로 모두 초기화

N = int(input()) # 색종이 갯수
for i in range(N):
    x, y = map(int, input().split())
    max_x = x+10
    max_y = y+10
    # 색종이에 해당하는 영역에 대해
    for j in range(x, max_x):   
        for k in range(y, max_y):
            paper[j][k] += 1    # 값을 더해준다

count_region = 0
for i in range(100):
    for j in range(100):
        if paper[i][j] != -1:   # -1이 아니면, 일단 겹치던 아니던 색종이가 붙은 영역이 됨
            count_region += 1   # 이 영역의 크기를 구함

print(count_region)

 

---