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

• 문제 링크
  • https://www.acmicpc.net/problem/2628

---

문제 풀이

• 세로로 잘리는 위치,가로로 잘리는 위치를 저장하기 위한 리스트 생성하고 0 넣어두기 (시작점)
• 가로인지 세로인지에 따라서 각각 세로리스트, 가로리스트에 저장
• 마지막 점 추가( 종이의 가로, 세로크기)
• 가로, 세로 리스트 정렬
• 가로/세로 리스트의 두점 (첫번째-두번째, 두번째 - 세번째,…)의 거리 구함
• 그 중에서 최대값을 구하고 각각 곱하면 정답!

---

소스 코드 (python)

C,R = map(int,input().split())  #세로, 가로 크기
N = int(input())    #자르는 횟수
Rarr = [0]          #세로로 잘리는 위치 저장
Carr = [0]          #가로로 잘리는 위치 저장
for i in range(N):
    t, p = map(int, input().split())    #t :가로인지 세로인지, p : 좌표
    if t == 0:
        Rarr.append(p)  #세로면 세로리스트에
    else:
        Carr.append(p)  #가로면 가로리스트에
Rarr.append(R)      #마지막 정점 추가
Carr.append(C)
Rarr.sort()         #정렬
Carr.sort()
maxR = 0
for i in range(1, len(Rarr)):
    gap = Rarr[i] - Rarr[i - 1]
    if maxR < gap:
        maxR = gap
maxC = 0
for i in range(1, len(Carr)):
    gap = Carr[i] - Carr[i - 1]
    if maxC < gap:
        maxC = gap
        
print(maxR * maxC)