파이썬 알고리즘
백준 2628 종이자르기 파이썬 풀이
뜻 지, 깨달음 오
2022. 9. 22. 17:58
https://www.acmicpc.net/problem/2628
2628번: 종이자르기
첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한
www.acmicpc.net
점선의 숫자들의 절댓값 차가 결국에는 잘린 종이의 넓이라는 점을 생각하였다.
가로 자르는 좌표 리스트, 세로 잘르는 좌표 리스트를 하나씩 만들고, 숫자를 각각 리스트에 넣었다.
그 다음에 끝값 (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)