[Python] 백준 2563번 문제 풀이 - 색종이

문제 링크

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

문제 이해

백준 2563번

가로와 세로가 100인 도화지에 가로와 세로가 10인 검정 색종이를 각 변에 평행하게 붙였을 때

도화지에 검정부분의 넓이가 어느정도인지 구하는 문제입니다.

아이디어

처음에는 검정색종이의 너비가 100이니 N*100을 해주고 겹치는 부분의 너비를 빼면 되겠다고 생각했지만 색종이가 100개라 이걸 일일히 다 계산하는 방법이 떠오르지 않았습니다.

어차피 도화지 가로세로가 100밖에 안되니 2차원 배열로 만들어서 검정색종이가 붙여지는 부분을 1로 바꾸고 도화지에서의 1의 합을 구하면 될 것이라 생각이 들었습니다.

또한 문제에서 색종이가 도화지를 벗어나는 일은 없다고 했기 때문에 조건도 필요없었습니다.

그래서 나온 아이디어는

1. 도화지를 100X100으로 초기화한다.
2. 입력의 x부터 x+10 과 y부터, y+10 까지 도화지의 좌표를 1로 바꾼다.
3. 도화지에서 1의 합을 구해서 출력한다.

입니다.

시간복잡도

이 아이디어의 시간복잡도는

색종이는 100개이고 한번 칠할때 최대 100번을 칠하기 때문에 → 10000번

도화지는 총 10000의 너비를 가지고 있어서 순회하면서 1의 합을 구하는 것 → 10000번

가능합니다.

코드 구현

그래서 이 아이디어를 코드로 구현하면 다음과 같습니다.

import sys
input = sys.stdin.readline

paper = [[0] * 100 for _ in range(100)]

n = int(input())

for _ in range(n):
    x, y = map(int, input().split())

    for i in range(y, 10+y):
        for j in range(x, 10 + x):
            paper[i][j] = 1

answer = sum(sum(row) for row in paper)

print(answer)