[Java] 백준 14215번 - 세 막대

문제 링크 : 백준 14215번 - 세 막대 자바

 

학교 수업 시간 또는 백준 5073번 - 삼각형과 세 변 문제에서 가장 긴 변의 길이보다 나머지 두 변의 길이의 합이 길지 않으면 삼각형의 조건을 만족하지 못한다고 배웠습니다. 즉, 가장 긴 변의 길이 >= 나머지 변의 길이 합 인 경우, 삼각형의 조건에 위배됩니다.

 

시각적으로 왜 그러지 못하는 것인지 보겠습니다.

변의 길이가 각각 1, 2, 3 인 경우, 가장 긴 변의 길이(3) >= 나머지 변의 길이 (1+2) 조건이므로 삼각형의 조건에 위배됩니다.

변의 각도를 이리저리 움직여보아도, 도저히 상대 변에 닿지 않습니다.

이러한 경우에, 우리는 가장 긴 변의 길이를 1 줄여주어 삼각형을 만들어줄 수 있습니다.

가장 긴 변인 3을 2로 줄이니 닿지 않던 1 변의 길이가 코앞에 있습니다. 문제의 조건에서, 각 막대의 길이를 마음대로 줄일 수 있다고 했으니 남는 부분을 잘라 가장 큰 둘레의 삼각형을 만들 수 있습니다. (변의 길이 1을 빼주기 전에는 삼각형 자체가 만들어지지 못했으므로, 현재의 둘레가 가장 큰 둘레가 됩니다.)

 

다만 1을 1번만 빼주는 것이 아니라, 위배 조건 긴 변의 길이 >= 나머지 변의 길이 합 이 만족하지 않을 때까지 1을  빼주어야 합니다. (입력으로 1 100 1 이 주어질 수 있음)

 

그런데 1 100,000,000,000,000 1 이 주어졌을 경우 1을 계속 빼주어야 할까요? 아닙니다.

가장 긴 변의 길이 >= 나머지 변의 길이 합 의 조건을 불만족 시키기만 하면 되므로, 가장 긴 변의 길이를 (나머지 변의 길이 합 - 1)으로 만들어주면 간단하게 좌항이 우항보다 1 작아지므로 바로 조건을 불만족하게 되어 삼각형을 만들 수 있습니다.

 

삼각형의 조건에 위배되지 않는 경우에는 각 변의 길이를 더해주기만 하면 됩니다.

참고 : 각 입력은 정수이기 때문에, 1을 빼주었습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] sides = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(sides);
        if (sides[2] >= sides[0] + sides[1]) {
            sides[2] = sides[0] + sides[1] - 1;
        }
        System.out.println(sides[0] + sides[1] + sides[2]);
    }
}