코팅테스트/백준 문제 모음
백준 2628번 파이썬 문제풀이(종이 자르기)
유지광이
2022. 1. 26. 23:25
728x90
해당 문제는 정렬을 이용한다는 것만 생각하면 쉽게 풀 수 있는 문제이다.(사실 정렬을 이용해야 한다는 걸 생각하기가 쉽지 않....)
문제의 풀이는 우선 가로의 길이와 세로의 길이를 각각의 리스트에 저장해 놓는 것이다. (단 입력받은 가로의 점은 세로길이를 구할 리스트에 입력받은 세로 점은 가로길이를 구하는 리스트에 저장해놓는다.) <- 이점이 상당히 중요
그 후 각각의 점들의 차를 구해주면 모든 사각형의 가로길이와 세로길이들이 각각 구해진다. 그 중 가장 큰 값을 골라서 곱해주면 된다.
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))
728x90