백준 2628번 종이자르기 파이썬

리뷰

처음 문제를 어떻게 접근해야 할지 막막했다. 2차원 배열을 생성해서 insert를 해줄까? 싶다가 너무 산으로 가는 것 같아서 조금 더 간단하게 생각해 보도록 했다.

문제 풀이

종이의 크기 x, y를 받고 가로와 세로 배열을 초기화 해 준다. 각 배열에 초기 인덱스값 0과 x 또는 y를 넣어주고 이후 자르는 좌표를 각 배열에 append 해준다. 모든 입력을 받았다면 가로 세로 배열을 각각 오름차순으로 정렬해 주고 해당 배열 내에서 길이가 가장 긴 값을 구해준 후 서로 곱해주면 최대 넓이가 된다.

가장 긴 값을 구하는 방법은 가로 세로 최대치를 저장할 변수를 초기화 해준 다음 정렬된 배열 내에서 인접한 두 인자의 차와 기존의 최대치를 비교하여 더 높은 값을 최대치로 갱신해 주면 된다.

참고 사항

종이의 크기를 가로 세로 배열에 넣어 주어야 정확한 답이 노출된다.

정답 코드

def q2628():
    # 백준 2628번 종이자르기 파이썬
    x, y = map(int, input().split())
    n = int(input())
    width = [0, x]
    height = [0, y]
    for _ in range(n):
        a, b = map(int, input().split())
        if a == 0:
            height.append(b)
        else:
            width.append(b)
    width.sort()
    height.sort()
    max_width = 0
    max_height = 0
    for i in range(1, len(width)):
        max_width = max(max_width, width[i] - width[i - 1])
    for i in range(1, len(height)):
        max_height = max(max_height, height[i] - height[i - 1])
    print(max_width * max_height)
q2628()