Algorithm/BAEKJOON

[백준 BOJ] 10163 색종이 (python)

DongKeun2 2022. 2. 16. 10:30

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

 

10163번: 색종이

평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘

www.acmicpc.net

 

🔥 처음 제출 코드 (53점)

N = int(input())

arr = [[0 for _ in range(1001)] for _ in range(1001)]

for n in range(1, N+1):
    x, y, w, h = map(int, input().split())

    for i in range(x, x+w):
        for j in range(y, y+h):
            arr[i][j] = n


for i in range(1, N+1):
    cnt = 0
    for j in range(1001):
        cnt += arr[j].count(i)
    print(cnt)

⭕ 해설

  1. 간단하게 모든 원소에 0을 저장한 1001x1001 크기의 2차원 배열을 만들어놨습니다.
  2. 그 뒤 입력받은 색종이가 차지하는 범위를 모두 덮어씌워 줍니다.
  3. 마지막 색종이까지 입력받고나서 남아있는 수를 세어주고 차례대로 출력합니다.

 

🔥 변경 후 제출코드 (100점)

import sys
input = sys.stdin.readline

N = int(input())

arr = [[0 for _ in range(1001)] for _ in range(1001)]

for i in range(1, N+1):
    x, y, w, h = map(int, input().split())

    for j in range(y, y+h):
        arr[j][x:x+w] = [i]*w


for i in range(1, N+1):
    cnt = 0
    for j in range(1001):
        cnt += arr[j].count(i)
    print(cnt)

 

아무리 찾아봐도 53점짜리 코드에서 틀린 부분을 못 찾아서 코드 수정없이 pypy로 돌렸더니 100점이 나왔습니다.

 

논리 구현이 틀린 것이 아니라 시간초과 때문에 53점을 받게 된 것 같아서

import sys를 넣어주고 색종이를 덮어씌우는 부분을 약간 만져주니 해결이 되었습니다.