[Java] 백준 14215번: 세 막대

문제 url:
세 막대

문제:

🤔 문제 알아보기

여기서는 삼각형의 정의를 한개 알아가야 풀 수 있는 문제이다.

• 삼각형의 가장 긴 변은 긴 변을 제외한 나머지 변의 합보다 작아야 한다.
• 즉 가장 긴 변을 C 나머지 변을 A, B로 지칭한다면
  • C < A + B 공식이 성립해야 한다는 의미이다.
• 또한 문제에서 각 막대기는 마음대로 줄일 수 있기 때문에 이 점을 유의해 삼각형을 만들어 보자.

🐱‍👤 실제 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 막대기를 3개 받으니 크기가 3인 배열 생성 후
        // hasMoreTokens()는 만약 반환할 토큰이 있다면 true를 반환.
        // 그래서 토큰을 stick 배열에 초기화
        int[] stick = new int[3];
        int i = 0;
        while(st.hasMoreTokens()) {
            stick[i] = Integer.parseInt(st.nextToken());
            i++;
        }

        // 배열을 오름차순으로 정렬
        Arrays.sort(stick);

        // 즉 삼각형이 아니라면 (긴 변이 이외의 변의 합보다 작아야 삼각형이 성립된다.)
        if(stick[2] >= stick[0] + stick[1]) {
            while(stick[2] >= stick[0] + stick[1]) {
                stick[2]--;
            }
            System.out.println(stick[0] + stick[1] + stick[2]);


        } else {
            System.out.println(stick[0] + stick[1] + stick[2]);
        }


    }
}

크게 어렵지 빠르게 간략히 코드 분석을 들어가보겠다.

😊 코드 분석

int[] stick = new int[3];
int i = 0;
while(st.hasMoreTokens()) {
       stick[i] = Integer.parseInt(st.nextToken());
       i++;
   }

// 배열을 오름차순으로 정렬
Arrays.sort(stick);

어김없이 등장한, 우리의 Array 오름차순!.
먼저 세 막대기이기 때문에 3의 크기를 가지는 배열을 생성
그런 다음 hasMoreTokens()는 토큰이 존재한다면 true를 반환하기에 이를 이용해
while문으로 배열에 토큰값들을 저장.

그 후 배열을 오름차순으로 정렬

핵심 알고리즘

---

 		// 즉 삼각형이 아니라면 (긴 변이 이외의 변의 합보다 작아야 삼각형이 성립된다.)
        if(stick[2] >= stick[0] + stick[1]) {
            while(stick[2] >= stick[0] + stick[1]) {
                stick[2]--;
            }
            System.out.println(stick[0] + stick[1] + stick[2]);


        } else {
            System.out.println(stick[0] + stick[1] + stick[2]);
        }

이번 문제의 핵심 알고리즘인데,
삼각형은 가장 긴 변의 길이가 이 외의 변 길이의 합보다 작어야 한다.
즉 C < A + B의 공식이 성립되어야 삼각형이라 할 수 있다.

이를 공식화 해서 풀어, 가장 긴 변이 이외의 변의 합보다 작아질 때까지 막대기를 줄여서 푸는 것이다.

🤢 코드 리팩토링

---

이번에는 좀 빠르게 푼다고 하드하게 풀었는데, 더 간단한 방법이 있어 공부해봤다.

import java.io.*;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        if (a+b<=c)
            c = a+b-1;
        else if (b+c<=a)
            a = b+c-1;
        else if (c+a<=b)
            b = c+a-1;

        System.out.println(a+b+c);


    }
}

if문은 어떤 변이 긴지를 확인하는 의문문으로,
아까 말했듯이 삼각형은 C < A + B 수식이 성립되어야 삼각형이라 정의할 수 있다.
이 점을 이용해서 둘레가 가장 길게 나올려면
A + B > C , C = A + B -1 값이면 둘레가 가장 길게 나올 수 있다.