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

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

2628번: 종이자르기

 

점선의 숫자들의 절댓값 차가 결국에는 잘린 종이의 넓이라는 점을 생각하였다.

가로 자르는 좌표 리스트, 세로 잘르는 좌표 리스트를 하나씩 만들고, 숫자를 각각 리스트에 넣었다.

그 다음에 끝값 (0이랑 넓이, 0이랑 높이)를 넣고 sort 해준다.

자른 부분의 좌표 차이의 곱이 넓이이다.

 

 

width, height = map(int, input().split())
cut_number = int(input())

cut = [list(map(int, input().split())) for _ in range(cut_number)]

garo_cut = []
sero_cut = []

for i in range(cut_number):
    if cut[i][0] == 0:
        garo_cut.append(cut[i][1])
    elif cut[i][0] == 1:
        sero_cut.append(cut[i][1])

garo_cut.append(height)
garo_cut.append(0)
sero_cut.append(width)
sero_cut.append(0)
garo_cut = sorted(garo_cut, reverse=True)
sero_cut = sorted(sero_cut, reverse=True)


MAX = 0
for i in range(1, len(garo_cut)):
    for j in range(1, len(sero_cut)):
        if (garo_cut[i-1]-garo_cut[i])*(sero_cut[j-1]-sero_cut[j]) >MAX:
            MAX = (garo_cut[i-1]-garo_cut[i])*(sero_cut[j-1]-sero_cut[j])
print(MAX)