Computer Science/Algorithm Problem

백준 알고리즘] 2959 - 거북이(COCI 2008/2009)

TwinParadox 2017. 11. 24. 07:55
728x90

시간 제한 : 1초

메모리 제한 : 128MB




문제

거북이는 이제 어떤 것에도 흥미를 느끼지 않는다. 그 이유는 거북이가 300년동안 살았고, 그 동안 모든 것들을 다 해보았기 때문이다. 거북이는 시간을 떼우는 무엇인가를 하려고 한다. 이번 주말에 거북이는 거북이 세계에서 매우 유명한 게임인 "가장 큰 직사각형 만들기"를 해보려고 한다.


이 게임을 시작하기 전에 거북이는 양의 정수 네 개를 머릿 속에 생각해야 한다. 한 방향으로 움직이기 시작하고 90도 회전한 뒤에 새로운 방향으로 움직인다. 이런 식으로 세 번 90도 회전을 하고, 네 번 앞으로 움직여서 선 분 네 개를 만들어야 한다.


거북이가 선분을 그릴 때 움직여야 하는 걸음의 수는 생각해 놓은 네 정수중 하나이다. 이 때, 한 정수를 각각 한 번씩 사용해야 한다. 거북이가 정수를 사용하는 순서에 따라서 다양한 모양이 만들어진다. 어떤 모양은 직사각형을 만들 수 없기도 한다.


거북이가 만들 수 있는 가장 큰 직사각형을 계산하는 프로그램을 작성하시오.






입력

첫째 줄에 거북이가 생각한 네 양의 정수 A, B, C, D가 주어진다. (0 < A, B, C, D < 100)






출력

첫째 줄에 거북이가 만들 수 있는 가장 큰 직사각형의 면적을 출력한다.






소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
	int arr[4];
	for (int i = 0; i < 4; i++)
		cin >> arr[i];
	sort(arr, arr + 4);
	cout << arr[0] * arr[2];
}






Tip

처음 보자마자 문제가 이해 되지 않는 사람이 있을 수 있다. 간단하게 말하자면 각기 다른 길이의 선들을 이용해 선이 남아도 좋으니 최대 크기의 직사각형을 만들어야 하는 문제다. 선이 아무리 길어도 평행한 다른 선분의 길이에 따라 직사각형의 크기가 결정되므로, 두 선분의 길이 차이가 최소화되는 방향으로 선택하면 된다.

728x90