[Python]백준_2628 : 종이자르기

Alal11·2022년 11월 7일

출처

https://www.acmicpc.net/problem/2628

문제

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

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

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

입력

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

출력

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

예제 입출력

알고리즘 분류

정렬

➡️문제 분석

가로와 세로의 배열을 각각 만들고, 그 안에 잘린 점선 값들을 넣어준다. 배열의 요소값들을 순서대로 빼주면 잘린 조각의 가로, 세로 길이가 된다.

➡️코드(⭕)

# 백준 2628번 종이자르기

x, y = map(int, input().split())

gr = [x, 0]              # 가로의 크기 배열
sr = [0, y]              # 세로의 크기 배열

line = int(input())

for i in range(line):                       # 점선 개수만큼 반복
    n, m = map(int, input().split())        # 가로인지 세로인지 나타내는 n과 점선번호 m을 입력

    if n == 0:                              # n이 0이면 가로로 자른다 (세로 길이에 영향)
        sr.append(m)                        # 세로 배열에 m 값 추가
    else:                                   # n이 1이면 세로로 자른다 (가로 길이에 영향)
        gr.append(m)                        # 가로 배열에 m 값 추가

gr = sorted(gr)
sr = sorted(sr)
result_list = []

for i in range(1, len(gr)):                 # 가로 배열의 길이만큼 i 반복
    for j in range(1, len(sr)):             # 세로 배열의 길이만큼 j 반복
        w = gr[i]-gr[i-1]                   # 가로 길이 w 구하기
        h = sr[j]-sr[j-1]                   # 세로 길이 h 구하기
        result_list.append(w*h)             # 가로, 세로의 곱을 구해 결과 리스트에 넣는다.

print(max(result_list))                     # 결과 리스트의 최댓값이 직사각형의 최대 넓이

➡️코드 분석

종이의 가로와 세로의 길이를 입력받고, 가로, 세로 배열을 만들어 준다.
점선의 개수만큼 반복하여 가로인지 세로인지 나타내는 n과 자를 점선 번호 m을 입력받는다.
n이 0이면 가로로 자르는데, 여기서 주의할 점!!
가로로 자르면 종이 조각의 세로 길이에 영향을 주기 때문에 세로의 배열에 m 값을 넣어준다.
n이 1일 때도 마찬가지로 세로로 자르니까 가로의 배열에 m 값을 추가한다.
가로, 세로 배열의 값을 정렬하고, 정렬된 리스트 값들은 잘린 직사각형의 번호이기 때문에 두 원소 값의 차를 이용해 가로와 세로의 길이를 구한다.
모든 조각의 넓이를 구한 다음 result_list에 넣고 최댓값을 출력한다.