[백준] 종이자르기 : 2628번 - Python

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

2628번: 종이자르기

 

 

 

문제의 접근 방법

 

가로 점선을 잘랐을 때는 그 값을 세로길이에 저장하고, 세로 점선을 잘랐을 때는 그 값을 가로길이에 저장해야 한다.

(ex) 3번 가로점선을 따라 자를 경우 그 잘린 값이 세로의 길이가 된다.

 

 

 

내가 막혔던 부분

 

- 문제의 접근 방법

 

 

 

문제 풀이 방법

 

(1) 가로와 세로 길이 w,h 입력받기

(2) 자를 횟수 n번 입력받기

(3) 나중에 길이를 직사각형의 길이를 계산하기 위해 width, height 배열 선언 (여기서 0은 나중에 길이 계산을 위해 시작 인덱스를 표시해 준 것)

(4) 자르는 횟수 n번만큼 반복문을 돌린 후 a (가로로 자를 것인지, 세로로 자를 것인지)와 b (몇 번 줄을 자를 것인지)를 입력받기

(5) 조건문을 통해 a가 0이라면(가로) b값을 세로 배열(height)에 추가하고 1이라면(세로) b값을 가로배열(width)에 추가

(6) 배열 width,height를 정렬하기

(7) 정렬된 리스트들은 잘린 인덱스 번호를 넣어둔 것이기 때문에 두 원소의 차를 이용해 가로와 세로 길이들을 구하기

(8) 그 값들을 곱했을 때 가장 큰 값이 직사각형의 최대 넓이!

 

 

 

소스코드

w,h = map(int, input().split())
n = int(input())
width = [0, w]
height = [0, h]

for _ in range(n):
    a,b = map(int, input().split())
    if a == 0:
        height.append(b)
    elif a == 1:
        width.append(b)

width.sort()
height.sort()

result = 0

for i in range(len(width)-1):
    for j in range(len(height)-1):
        x = width[i+1] - width[i]
        y = height[j+1] - height[j]
        result = max(result, x*y)

print(result)