[n2628] 종이 자르기 in python

---

뚜렷한 방법이 떠오르지 않아서

구하는 풀이를 직접 적어보고 찾아내었다.

 

위 예제로 생각해보았다.

행 = 8, 열 = 10

 

1번 상자

: 2 X 4

 

2번 상자

: 2 X (10-6)

 

3번 상자

: (3-2) X 4

 

4번 상자

: (3-2) X (10-6)

 

5번 상자

: (8-3) X 4

 

6번 상자

: (8-3) X (10-4)

 

 

행과 열을 각각 리스트로 받으면

행 = [0,2,3,8]

열 = [0,4,10]

 

행[i+1]-행[i] || 열[j+1]-열[j] 

위 식을 이용하면

방금 풀었던 풀이대로

프로그램 구현이 가능해진다.

 

 

sort() 과정은 필수

 

col, row = map(int, input().split())
rows = [0, row]  # 행
cols = [0, col]  # 열

for _ in range(int(input())):
    now, num = map(int, input().split())
    if now:  # 세로
        cols.append(num)
    else:
        rows.append(num)

rows.sort()
cols.sort()
answer = 0

for i in range(len(rows) - 1):
    for j in range(len(cols) - 1):
        answer = max(answer, (cols[j + 1] - cols[j]) * (rows[i + 1] - rows[i]))

print(answer)