[BOJ] 2628번 종이자르기 - 파이썬

📒 문제

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

<그림 1>: https://www.acmicpc.net/problem/2628

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

<그림 2>: https://www.acmicpc.net/problem/2628

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

입력

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

출력

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

✏️ 풀이

이 문제는 비교적 쉬운 편이었다. (무슨무슨 알고리즘이 아니라 그냥 풀면 되어서...)
아무튼 문제에서 주어진대로, 넓이를 계산하면 되는 문제였기 때문에 가로랑 세로를 구해서 곱하고 그 중 가장 큰 값을 출력해주는 방식으로 문제를 해결했다.

x, y = map(int, input().split())
garo = [0, x]  # 가로
sero = [0, y]  # 세로
cut_times = int(input())
for i in range(cut_times):
    num, line_num = map(int, input().split())
    if num == 0:  
    # num이 0이면 문제에서 가로로 '자르는' 점선이라 했으므로, 이 선은 엄연히 세로에 속하는 선이다.
        sero.append(line_num)
    else:  
    # 반대의 경우도 마찬가지다. 속지 말자.
        garo.append(line_num)

garo = sorted(garo)
sero = sorted(sero)
result_list = []
for i in range(1, len(garo)):
    for j in range(1, len(sero)):
        width = garo[i] - garo[i-1]
        height = sero[j] - sero[j-1]
        result_list.append(width * height)

print(max(result_list))

위의 코드를 통해 29200kb, 72ms로 적당한 결과를 얻을 수 있었다.