세 개의 수 a, b, c가 주어져 있다고 가정해 봅시다. 우리는 임의의 비퇴화(non-degenerate) 단순 사변형 모양으로 닫힌 울타리를 만들려고 하며, 길이가 각각 a, b, c인 세 변은 이미 확보한 상태입니다. 이제 남은 한 변 d의 길이를 찾아야 합니다.
예를 들어 입력이 a = 12, b = 34, c = 56이라면 출력은 100이 됩니다. 물론 사변형 조건만 만족한다면 이 외에도 다른 정답이 존재할 수 있습니다.
문제 해결 접근 방법
사변형이 실제로 존재하려면 가장 긴 변의 길이가 나머지 세 변의 길이 합보다 엄격하게 작아야 한다는 기하학적 조건을 만족해야 합니다. 세 변 a, b, c가 모두 양의 정수라면, 네 번째 변을 d = a + b + c - 2로 선택하는 것이 가장 간단한 방법입니다.
d = a + b + c - 2를 선택하면 다음 두 조건이 항상 성립합니다.
- d는 명백히 a + b + c보다 작으므로, d가 가장 긴 변인 경우에도 조건을 만족합니다.
- a, b, c 중 하나가 가장 긴 변이라 하더라도, 나머지 세 변의 합에 d = a + b + c - 2가 더해지므로 부등식이 항상 성립합니다.
따라서 이 문제는 다음 한 줄의 계산으로 해결할 수 있습니다 −
return a + b + c - 2
예제 구현
다음 C++ 구현을 통해 더 잘 이해할 수 있습니다 −
#include<bits/stdc++.h>
using namespace std;
int solve(int a, int b, int c){
return a+b+c-2;
}
int main(){
int a = 12;
int b = 34;
int c = 56;
cout << solve(a, b, c) << endl;
}입력
12, 34, 56
출력
100
정리
이 프로그램은 세 변의 합에서 2를 뺀 값을 네 번째 변으로 반환함으로써, 항상 유효한(비퇴화된) 사변형을 만들 수 있는 답을 보장합니다. 시간 복잡도는 O(1)로, 입력 크기와 무관하게 즉시 결과를 계산할 수 있다는 장점이 있습니다.