BOJ 16207 : 직사각형

• 문제 링크 : boj.kr/16207
• 난이도 : G3
• 태그 : 정렬, 그리디

16207번: 직사각형

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<ll> arr(n);

    for(auto &u : arr) cin >> u;
    sort(all(arr), greater<ll>());

    ll ans = 0;
    ll a = 0, b = 0;
    for(int i = 0; i + 1 < n; i++) {
        if(arr[i] - arr[i+1] <= 1) {
            if(a == 0) a = arr[i+1];
            else b = arr[i+1];
            i++;
        }
        if(a != 0 && b != 0) {
            ans += a*b;
            a = 0;
            b = 0;
        }
    }
    cout << ans;

    return 0;
}

---

풀이

조건에 따르면 크기가 1 차이나는 두 막대가 서로 마주보는 변이 될 수 있다. 서로 마주보는 변이 될 수 있는 막대의 쌍만 적절하게 골라주면 된다.

이 막대의 길이는 길면 길수록 좋으므로 긴 막대부터 조건을 만족하는지 확인한다. 긴 순서대로 조건을 만족하는 막대쌍을 둘씩 짝지어 직사각형을 만들어주면 된다.