프로그래머스(programmers) 최소직사각형 python 정답 [완전 탐색]

프로그래머스(programmers) 최소직사각형 python 정답 [완전 탐색]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

문제 정답

입출력 예

sizes	result
[[60, 50], [30, 70], [60, 30], [80, 40]]	4000
[[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]	120
[[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]	133

정답 코드

def solution(sizes):
    return max(map(max,sizes)) * max(map(min,sizes))

문제 해설

아래와 같은 직사각형들이 있다 가정하자. 

세로(혹은 한 변)이 최대인 직사각형이 있다.

다른 직사각형들의 가장 긴 한 변을 해당 변 쪽으로 정렬할 수 있을 것이다.

긴 변들을 한 쪽으로 정렬하여 겹쳐보았다.

작은 변들을 겹쳐둔 곳을 보니(가로 또는 다른 한변)

작은 변들의 최대값이 전체를 둘러싸는 직사각형의 너비를 결정할 것 같다.

따라서 긴변의 최대값괴 작은변의 최대값을 곱하면 (max(map(max,sizes)) * max(map(min,sizes))) 정답이 된다.