백준 16207(직사각형)

https://www.acmicpc.net/problem/16207

16207번: 직사각형

 

스터디 모의고사를 봤는데 아쉽게 종료시각 직전에 풀어서 오류를 못 고쳐서 못 낸 문제

 

아무튼 아쉽다

 

사실 어제 코포에서 직사각형과 정사각형을 만드는 문제가 있어서 조금 더 쉽다고 생각했다.

 

한 변을 딱 한번만 1을 뺄 수 있을 때에 

그 변들로 구성하는 직사각형

넓이의 합이 최대가 되도록 하는 넓이의 합을 구하는 문제.

 

 

먼저 넓이의 합이 언제 최대가 되는지 생각을 해봐야한다. 

 

직사각형의 넓이는 변의 곱셈으로 이루어지는데 

 

곱셈이란 어떤 값을 몇 번 더하는 셈이다. 

 

따라서 곱셈의 값이 커지려면 큰 수를 많이 더 하면 곱셈의 값이 더 커진다. 

 

그래서 가장 큰 변끼리 곱을 하면 최대의 넓이가 나온다. 

그렇다면 만약에 큰 변끼리 곱을 해서 문제가 생기는 경우

 

만약에 큰 변끼리 곱을 해서 넓이는 최대가 될지언정 만드는 직사각형의 갯수에 차이가 생겨서 큰 변끼리 곱을 하면 안되는 경우를 생각해보았지만 불가능했다.

 

그래서 그냥 정렬을 하고, 큰 것부터 변을 하나하나 구하고, 두 변이 모두 완성되면 곱을 해서 정답에 합했다.

 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 10005

int N;
long long int sum, l1, l2;
long long int makde[MAX];


int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> makde[i];
	}
	sort(makde, makde + N);
	int i = N - 1;
	while(i>=0){
		if ((makde[i] - makde[i - 1]) == 0) {
			if (l1 == 0)
				l1 = makde[i];
			else
				l2 = makde[i];
			i-=2;
		}
		else if ((makde[i] - makde[i - 1]) <= 1) {
			if (l1 == 0)
				l1 = makde[i-1];
			else
				l2 = makde[i-1];
			i -= 2;
		}
		else if ((makde[i] - makde[i - 1]) > 1) {
			i--;
		}
		if (l1 != 0 && l2 != 0) {
			sum += l1 * l2;
			l1 = 0;
			l2 = 0;
		}
	}
	cout << sum << "\n";
}