백준 2628. 종이자르기

2628. 종이자르기

2628번: 종이자르기

---

입력

• 첫줄에는 종이의 가로와 세로 길이가 주어진다.
• 둘째 줄에는 잘라야하는 점선의 수가 주어진다.
• 셋째줄부터 마지막 줄까지 점선이 주어진다. (첫 숫자 0 - 가로, 1 - 세로), (두번째 숫자 - 점선 번호)

---

문제 풀이

• 종이를 잘랐을 때 세로 간격과 가로 간격을 모두 구한 후, 가로 최대값과 세로 최대값을 구하여 답을 도출하였다.

M, N = [*map(int, input().split())]     # M - 가로, N - 세로

num = int(input())  # 자르는 수
garo = [0]          # 가로로 자르는 위치 저장할 리스트
sero = [0]          # 세로로 자르는 위치 저장할 리스트
garo_dif = []       # 가로방향으로 자르는 위치 차이 저장할 리스트
sero_dif = []       # 세로방향으로 자르는 위치 차이 저장할 리스트
maxx = 0            # 면적 최대값 저장할 변수

for i in range(num):        
    dir, ind = [*map(int, input().split())] # dir - 방향(0이면 가로 방향, 1이면 세로방향), ind - 어디를 자를지
    if dir == 0:                            # 방향에 맞는 리스트에 저장
        garo.append(ind)   
    else:
        sero.append(ind)
garo.append(N)                              # 가로 방향의 마지막 인덱스 추가
sero.append(M)                              # 세로 방향의 마지막 인덱스 추가
garo.sort()                                 # 오름차순으로 정렬
sero.sort()

for i in range(len(garo)-1):                # 각 방향에서 자른 위치 간격 구해서 저장
    garo_dif.append(garo[i+1]-garo[i])
for i in range(len(sero)-1):
    sero_dif.append(sero[i+1]-sero[i])
for i in garo_dif:                          # 가로 방향 간격
    for j in sero_dif:                      # 세로 방향 간격
        if maxx < i*j:                      # 두 개의 곱이 기존 면적보다 크면 갱신
            maxx = i*j
print(maxx)