C++로 삼각형을 만들기 위해 막대 길이를 늘려야 하는 최소 시간(분) 계산하기

문제 설명

세 개의 숫자 a, b, c가 주어졌다고 가정해 보겠습니다. 각각 길이가 a, b, c인 세 개의 막대가 있으며, 1분마다 임의의 막대 하나를 선택해 길이를 1cm씩 늘릴 수 있습니다. 단, 막대를 자르거나 줄일 수는 없습니다. 목표는 이 세 막대로 삼각형을 만들 수 있을 때까지 걸리는 최소 시간(분)을 구하는 것입니다.

예를 들어 입력이 a = 2, b = 3, c = 5라면 출력은 1이 됩니다. a 또는 b 중 아무거나 하나를 1만큼 늘리면 (a + b) > c 조건을 만족하는 삼각형을 만들 수 있기 때문입니다. 즉, 1분이면 충분합니다.

접근 방법

삼각형이 성립하려면 삼각형 부등식, 즉 가장 긴 변의 길이가 나머지 두 변의 길이 합보다 작아야 한다는 조건을 만족해야 합니다. 따라서 다음과 같은 단계로 문제를 해결할 수 있습니다.

1. 배열 A = {a, b, c}를 정의합니다.
2. 배열 A를 오름차순으로 정렬합니다.
3. max(A[2] - A[1] - A[0] + 1, 0) 값을 반환합니다.

정렬 후 A[2]는 가장 긴 변이 됩니다. 두 짧은 막대의 합(A[0] + A[1])이 가장 긴 막대(A[2])에 비해 얼마나 부족한지 계산하고, 엄격한 부등식(A + B > C)을 만족하도록 1을 더해 줍니다. 이미 삼각형을 만들 수 있는 상태라면 결과값이 0 이하가 되므로, max 함수를 사용해 0을 반환하도록 처리합니다.

C++ 구현 예제

아래 코드를 통해 더 쉽게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(int a, int b, int c) {
    vector<int> A = { a, b, c };
    sort(A.begin(), A.end());
    return max(A[2] - A[1] - A[0] + 1, 0);
}
int main() {
    int a = 2;
    int b = 3;
    int c = 5;
    cout << solve(a, b, c) << endl;
}

입력

2, 3, 5

출력

1

복잡도 분석

이 풀이는 원소가 3개뿐인 배열을 정렬하고 단순한 산술 연산만 수행하므로, 시간 복잡도는 O(1), 공간 복잡도 역시 O(1)로 매우 효율적입니다. 입력 크기와 무관하게 일정한 시간 안에 답을 구할 수 있습니다.