백준 10163번 색종이 파이썬

리뷰

상위 난이도 문제인 색종이와 색종이-2 보다 평면의 길이가 커서 시간 초과가 나지 않을까 했지만 다행히 시간초과가 나진 않았다. 해당 문제를 이해하고 색종이와 색종이-2에 접근한다면 해당 문제들을 쉽게 풀 수 있을 것 같다.

문제 풀이

마지막으로 들어온 종이는 온전히 자기 넓이를 가져야 하므로 각 좌표와 넓이를 리스트로 받아와 준 후 한번 reverse를 해 주었다. 1001 * 1001 크기의 2차원 배열을 생성해준 후 해당 위치의 값이 0일 경우 1로 변경해줌과 동시에 넓이를 1 더해주었다. 그리고 내부 for문이 종료될 때 얻은 넓이 값을 별도의 리스트에 저장, 모든 종이의 넓이를 구해준 후 넓이가 저장된 리스트를 다시 reverse하여 각각의 넓이를 출력해 주었다.

추천 반례

없음

정답 코드

def q10163():
    # 백준 10163번 색종이 파이썬
    n = int(input())
    lst = [list(map(int, input().split())) for _ in range(n)]
    lst.reverse()
    result = []
    dp = [[0] * 1001 for _ in range(1001)]
    for i in lst:
        width = 0
        for j in range(i[0], i[0] + i[2]):
            for k in range(i[1], i[1] + i[3]):
                if dp[j][k] == 0:
                    dp[j][k] = 1
                    width += 1
        result.append(width)
    result.reverse()
    for i in result:
        print(i)
q10163()