[백준] 2959 - 거북이

문제 링크

2959번: 거북이 (acmicpc.net)

2959번: 거북이

코드 

#include <iostream>
#include <algorithm>

int main()
{
	int a[4];
	std::cin >> a[0] >> a[1] >> a[2] >> a[3];
	std::sort(a, a + 4);
	std::cout << a[0] * a[2];
}

 

풀이 해설

직사각형을 만들기 위해서는 4개에 변이 필요하다.

$A,B,C,D (0 < A,B,C,D \leq 100)$

여기서 이 문제의 핵심은

$A=Min(상,하) * Min(좌,우)$

이렇게 정의가 된다.

상이 5,하가 4면 상을 5로 잡으면 하가 1만큼 부족하고 반대로 4를 기준으로 잡으면 5를 1칸 잘라 4로 만들면 된다.

즉 값 2개로 가장 높은 값을 만드는 게 이 문제의 중요한 포인트다.

 

4개에 입력에서 가장 높은값을 만드는 방법은

$A,B,C,D$가 오름차순 정렬 되고 $x_0,x_1,x_2,x_3$ 이 되었다고 가정하자

 

$A = Min(x_0,x_1) * Min(x_2,x_3)$

$A = x_0 * x_2$

이렇게 정의가 가능하다.

왜 $x_0,x_2$이면 다른 후보로는 $x_0,x_1$이 있다.

 

$A_0 = x_0 * x_2$

$A_1 = x_0 * x_1$

이 있다고 가정하면

 

$A_0 \geq A_1$

$x_0 * x_2 \geq x_0 * x_1$

$x_2 \geq x_1$

오름차순 정렬이므로 x_1보다 x_2가 크거나 같은건 참이다.

 

고로 이 문제의 정답은

$A = x_0 * x_2$

이다.