백준 2628번 파이썬 문제풀이(종이 자르기)

 

---

해당 문제는 정렬을 이용한다는 것만 생각하면 쉽게 풀 수 있는 문제이다.(사실 정렬을 이용해야 한다는 걸 생각하기가 쉽지 않....)

 

문제의 풀이는 우선 가로의 길이와 세로의 길이를 각각의 리스트에 저장해 놓는 것이다. (단 입력받은 가로의 점은 세로길이를 구할 리스트에 입력받은 세로 점은 가로길이를 구하는 리스트에 저장해놓는다.) <- 이점이 상당히 중요

 

그 후 각각의 점들의 차를 구해주면 모든 사각형의 가로길이와 세로길이들이 각각 구해진다. 그 중 가장 큰 값을 골라서 곱해주면 된다.

 

width, height = map(int, input().split())
N = int(input())
info_width = [0, width]  # 가로 길이를 구하기위해 점들을 저장할 리스트
info_height = [0, height]  # 세로 길이를 구하기 위해 점들을 저장할 리스트
for i in range(N):  # 입력 받은 개수 만큼 반복문 돈다.
    temp = list(map(int, input().split()))

    if temp[0] == 0:  # 만약 가로점을 입력받았다면
        info_height.append(temp[1])  # 세로 길이 리스트에 값들을 저장해준다.
    else:  # 만약 세로 점을 입력받았다면
        info_width.append(temp[1])  # 가로 길이 리스트에 세로길이들을 저장해준다.

info_width.sort()  # 오름차순 정렬
info_height.sort()  # 오름차순 정렬

width_list = []  # 전체 길이에서 잘라진 가로 길이들을 담을 리스트 선언
height_list = []  # 전체 길이에서 잘라진 세로 길이들을 담을 리스트 선언

# 각각의 나눠진 가로 길이 계산
for i in range(len(info_width) - 1):
    width_list.append(info_width[i + 1] - info_width[i])

# 각각의 나눠진 가로 세로 계산
for i in range(len(info_height) - 1):
    height_list.append(info_height[i + 1] - info_height[i])


# 각각 가장 긴 세로,가로 길이를 곱해준다.
print(max(height_list) * max(width_list))