백준 10163 색종이 (파이썬)

풀이 및 해석(주석)

N = int(input())
info = [list(map(int, input().split())) for _ in range(N)]

max_r = max_c = 0
for n in info:                  # 1000행, 1000열을 미리 만들기 싫어서 최대 행값과 열값을 뽑아준다.
    if (n[2]+n[0]) > max_c:
        max_c = (n[2]+n[0])
    if (n[3]+n[1]) > max_r:
        max_r = (n[3]+n[1])

arr = [[0]*(max_c+1) for _ in range(max_r+1)]

for s in range(N):
    r, c, w, h = info[s][0], info[s][1], info[s][2], info[s][3],
    for i in range(c, c+h):              # 이 부분에서 시간초과 문제가 발생한다.
        arr[i][r:r+w] = [s+1]*w          # 열을 하나하나 바꾸지말고, 원하는 만큼의 열을 한번에 바꿔준다.
# for line in arr:
#     print(*line)
for num in range(1, N+1):
    sums = 0
    for i in arr:
        sums += i.count(num)
    print(sums)

 

---

후기

IM대비 문제집에 있는 문제여서 실행 시간을 신경 안썻는데, for문을 3중으로 돌리면 시간초과가 나는 것 같다.

또한, 나는 일부러 1000x1000배열을 만들기 싫어서 가장 큰 값의 행, 열을 뽑아 배열을 만들어 줬는데, 

사실 채점할 때는 1000개의 테스트 케이스도 할 것이기 때문에 큰 의미는 없었던 것 같다.