[python] 백준 2628 :: 종이자르기

종이자르기

# 문제
아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다.

점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다.

입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.

# 입력
첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.

# 출력
첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다.

풀이

import sys
w, h = map(int, input().split())

# 가로/세로의 처음 점, 끝 점, 잘린 점들을 담을 배열
w_list = [0, w]
h_list = [0, h]

for _ in range(int(input())):
    direction, number = map(int, sys.stdin.readline().split())
    # 세로로 잘린 것들은 가로의 잘린 점들을 담을 배열에 담는다.
    if direction == 1:
        w_list.append(number)
    # 반대로 가로로 잘린 것들은 세로 배열에 담는다.
    else:
        h_list.append(number)

# 처음 점, 잘린 점들, 끝점 순서로 오도록 오름차순으로 정렬한다.
w_list.sort()
h_list.sort()

# 점들 간의 간격을 구해서 가장 큰 값끼리 곱한다.
print(
    max([w_list[i+1] - w_list[i] for i in range(len(w_list)-1)])
    *
    max([h_list[i+1] - h_list[i] for i in range(len(h_list)-1)])
)

1. 가로 세로 각각 처음 점, 끝 점, 잘린 점들을 담을 배열을 만든다.

2. 점들을 담은 후 오름차순으로 정렬한다.
   🤔Why? 다음 단계에서 점들의 간격을 구할 건데, 연속되는 점들의 간격을 구해야 하므로 정렬을 먼저 수행한다.

3. 가로 세로 배열에서 요소들의 간격들을 각각 구하고, 각 배열에서 제일 큰 값의 곱을 출력한다.