[python] 직사각형 만들기

문제

N개의 막대기 중 일부를 잘 배치해서 직사각형을 만들고자 한다.

 

직사각형을 만들기 위해서는 길이가 같은 막대기 두 쌍이 필요하다. 같은 쌍에 속한 막대기들을 마주 보게 배치하고, 다른 쌍에 속한 막대기들을 수직으로 배치하면 직사각형을 만들 수 있다. 길이가 a인 막대기와 길이가 b인 막대기 쌍을 사용해서 직사각형을 만들었을 때, 만들어진 직사각형의 넓이는 ab이다.

 

하나의 막대기는 하나의 직사각형을 만드는 데만 이용할 수 있고, 가능한 많은 직사각형을 만들면서도 직사각형들의 넓이 합이 최대가 되고자 한다. 가지고 있는 막대기의 정보가 주어졌을 때, 만들 수 있는 직사각형들의 넓이 합의 최댓값을 구하시오.

 

 

입력

첫째 줄에는 가지고 있는 막대기의 개수 N이 주어진다.

둘째 줄에는 S1, ..., Sn 이 공백을 두고 주어진다. Si는 가지고 있는 막대기의 길이를 의미한다.

• 1 ≤ N ≤ 10^6
• 1 ≤ Si ≤ 10^6
• 입력에서 주어지는 모든 수는 정수이다.

 

import sys
input = sys.stdin.readline

n = int(input())

stick = list(map(int, input().split()))
stick.sort(reverse = True)

sqr = []
result = 0

i = 0
while i < len(stick)-1:
	if stick[i] == stick[i+1]:
		sqr.append(stick[i])
		if len(sqr) == 2:
			result += sqr[0]*sqr[1]
			sqr = []
		i += 2
		continue
	i += 1
			
print(result)

큰 값들 순으로 나열을 한 후 쌍을 이뤄 직사각형 넓이를 구하면 자연스럽게 답이 나온다.

 

 

※출처

https://multicampus-kdt.goorm.io/lecture/38996/멀티잇-코딩테스트-러닝클래스-python-6월반