[Python/그리디] 3.직사각형 만들기
출처: 구름 알고리즘 먼데이 챌린지 8주차
문제
구름이는 N개의 직선 막대기를 가지고 있다. 구름이는 이 막대기들 중 일부를 잘 배치해서, 직사각형을 만들고자 한다.
직사각형을 만들기 위해서는 길이가 같은 막대기 두 쌍이 필요하다. 같은 쌍에 속한 막대기들을 마주 보게 배치하고, 다른 쌍에 속한 막대기들을 수직으로 배치하면 아래 그림과 같이 직사각형을 만들 수 있다. 길이가 a인 막대기와 길이가 b인 막대기 쌍을 사용해서 직사각형을 만들었을 때, 만들어진 직사각형의 넓이는 ab이다.
하나의 막대기는 하나의 직사각형을 만드는 데만 이용할 수 있고, 구름이는 가능한 많은 직사각형을 만들면서도 직사각형들의 넓이 합이 최대가 되기를 원한다. 구름이가 가지고 있는 막대기의 정보가 주어졌을 때, 구름이가 만들 수 있는 직사각형들의 넓이 합의 최댓값을 구하시오.
입력
첫째 줄에는 구름이가 가지고 있는 막대기의 개수를 의미하는 정수 N(1<=N<=10^6) 이 주어진다.
둘째 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 각 정수는 구름이가 가지고 있는 막대기의 길이를 의미하고, 모든 막대기의 길이는 1 이상 10^6 이하이다.
출력
구름이가 만들 수 있는 직사각형들의 넓이 합의 최댓값을 출력하시오.
| 예제 입력 | 예제 출력 |
| 4 4 8 4 8 |
32 |
| 8 2 4 6 8 2 4 6 8 |
56 |
| 5 1 2 3 4 5 |
0 |
풀이
최적의 전략을 맞아서 문제를 해결하는 그리디(greedy) 알고리즘 문제이다.
1. 일단 a라는 막대기 하나인 경우에는 직사각형을 만들 수 없으므로 무시하고,
a 막대기가 3 이상의 홀수 개인 경우 짝수개로 취급을 해준다.
2. a,b,c,d 네 개의 막대기가 있고 a <= b <= c <= d 인 경우,
a*b + c*d일 때 넓이의 최댓값이다.
따라서 막대기 쌍의 길이가 긴 것부터 순서대로 직사각형을 만들어주면 된다.
1번이 구현하기 까다로웠는데 collections의 Counter를 사용해서
value가 2 이상일 때까지만 counter에서 value를 2개씩 빼면서, 처리된 막대기쌍을 담는 리스트 pair에 key를 append했다.
'''
N개의 직선 막대기. 네 개의 막대기로 하나의 직사각형을 만든다.
막대기를 가지고 만들 수 있는 직사각형 넓이의 합이 최대가 되게
같은 직선이 모두 2개씩이 아니라면?
'''
from collections import Counter
import sys
input = sys.stdin.readline
N = int(input())
lines = list(map(int, input().split()))
# 1. 막대기 쌍 처리
pair = [] # lines 후처리 (1, 홀수 처리)
counter = Counter(lines)
#print(counter)
for line in counter.keys():
while counter[line] > 1:
counter[line] -= 2
pair.append(line)
#print(pair)
# 2. 직사각형들 넓이 계산
pair.sort(reverse=True)
ans = 0
for i in range(0, len(pair)-1, 2):
ans += pair[i] * pair[i+1]
print(ans)다른 풀이
Counter를 직접 구현한 경우
import sys
input = sys.stdin.readline
N = int(input())
lines = list(map(int, input().split()))
# 1. 막대기 쌍 처리
pair = [] # lines 후처리 (1, 홀수 처리)
length = max(lines)
counter = [0 for _ in range(length+1)]
for line in lines:
counter[line] +=1
#print(counter)
for line in range(len(counter)):
while counter[line] > 1:
counter[line] -= 2
pair.append(line)
#print(pair)
# 2. 직사각형들 넓이 계산
pair.sort(reverse=True)
ans = 0
for i in range(0, len(pair)-1, 2):
ans += pair[i] * pair[i+1]
print(ans)