문제

구름이는 N개의 직선 막대기를 가지고 있다. 구름이는 이 막대기들 중 일부를 잘 배치해서, 직사각형을 만들고자 한다.

 

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

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


입력

첫째 줄에는 구름이가 가지고 있는 막대기의 개수를 의미하는 정수 N(1 <= N <= 10^6)이 주어진다.

 

둘째 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 각 정수는 구름이가 가지고 있는 막대기의 길이를 의미하고, 모든 막대기의 길이는 1이상 10^6이하이다.


다시 한번 그리디 알고리즘에 유형에 연습이 부족하다는 것을 깨닫게 되는 문제였다.

문제를 읽고 최대한 큰 길이의 막대를 우선적으로 사용하여 직사각형을 구성한다는 것은 직관적으로 이해하였다.

하지만, 같은 길이의 쌍만을 사용하여 직사각형을 만들 수 도 있다는 점을 관가하면서 구현 방향에서 어려움을 느꼈다.

가령 6 6 8 8 8 8 과 같이 입력이 주어질 경우 {8, 8}, {8, 8}의 쌍으로 직사각형을 구성할 수 있는데 {6, 6}, {8, 8}로 구성해야 한다고 잘못 판단하였다.

 

따라서 이번에는 제공된 정답 코드를 풀이하고자 한다.

#include <iostream>
typedef long long ll;
using namespace std;

const int MAX = 1000007;
int cnt[MAX];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll N, ans = 0;
    cin >> N;
    //1.주어진 입력에 따라 각 길이의 막대 개수를 저장
    for (int i = 0; i < N; ++i) {
        int s;
        cin >> s;
        cnt[s]++;
    }
    int pv = 0;
    for (int i = 1000000; i > 0; --i) {
        while (cnt[i] > 1) {
            if (pv) {
                ans += (ll)pv * i;
                pv = 0;
            }
            else pv = i;
            cnt[i] -= 2;
        }
    }
    cout << ans;
    return 0;
}

 

입력 크기가 최대 백만(1,000,000)일 경우 문제의 설정된 메모리 제한을 초과할 수 있다고 판단하여 map을 사용해야 한다고 생각했다.

하지만, 테스트 해본 결과 백만의 크기의 배열을 지역변수로 선언하여 스택영역에서 생성하지 않고 전역변수로 선언하여 데이터 영역에 생성해 주면 런타임 에러가 발생하지 않는 것을 확인하였다.

지금까지의 경험상 대부분의 문제에서 스택 영역에서의 메모리 제한은 까다로운 것으로 확인되었고 가능하면 전역변수로 선언하는 것을 지향하도록 하자.

 

1)주어진 입력에 따라 각 길이의 막대 개수를 저장해준다. 

2)최대한 넓이가 큰 직사각형을 만들기 위해 큰 길이의 막대를 우선적으로 사용한다.

3)해당 길이의 막대의 개수가 2개 이상을 경우만 쌍을 이룰 수 있음에 주의하자.

4-1)조건 3을 만족하고 이미 채택된 변(pv)가 있다면 현재 막대를 나머지 변으로 사용하여 직사각형 넓이를 구해준다.

4-2)조건 3을 만족하고 아직 채택된 변이 없다면 현재 막대를 변으로 채택한다.

 

추가적으로 변 pv를 long long 형으로 선언해주거나

int형으로 선언하되 넓이를 구하는 과정에서 형변환을 해주어야 하는 것에 주의하자.