[백준] 1448번 삼각형 만들기 / C++ Java

문제 : https://www.acmicpc.net/problem/1448

C++

#include<iostream>
#include<algorithm>
using namespace std;

// 가장 긴 변의 길이가 댜른 두변의 합보다 작아야 한다.
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    int arr1[1000000];
    for(int i = 0; i < n; i++) {
        cin >> arr1[i];
    }
    sort(arr1, arr1+n, greater<int>());
    int total = 0;
    for(int j = 0; j <= n / 2; j++) {
        if(arr1[j] < arr1[j+1] + arr1[j+2]) {
            total = arr1[j] + arr1[j+1] + arr1[j+2];
            cout << total;
            break;
        }
    }
    if(total == 0) {
        cout << -1;
    }
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        Integer [] arr = new Integer[n];

        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr, Collections.reverseOrder());

        int total = -1;
        for(int j = 0; j < n-2; j++) {
            if(arr[j] < arr[j+1] + arr[j+2]) {
                total = arr[j] + arr[j+1] + arr[j+2];
                break;
            }
        }
        bw.write(total + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

문제풀이

• 삼각형이 되기 위한 조건은 가장 긴 변의 길이가 다른 두 변의 합보다 작아야 한다. 세 변의 길이의 합의 최댓값을 구하기 위해 먼저 변의 길이를 입력받고, 내림차순으로 정렬한다. 가장 앞에 세 변부터 비교하면서, 삼각형의 구성 조건에 적합하는지 확인한다. 그리고 모든 변이 삼각형을 만들기 부적합하다면 -1을 출력한다.

Comment

• Java에서 정렬하는 방법에 대해 배웠다. 또한 c++ 코드에서는 for문의 범위를 j <= n/2라고 했는데, 이렇게 되면 j가 n-2일 경우 arr[j+2]가 arr[n]이 되면서 arr 범위를 벗어난다. 따라서 for문의 범위를 j < n - 2로 변경해야 한다.

참고블로그 : https://velog.io/@min-ji99/JAVA-%EB%B0%B0%EC%97%B4-%EC%A0%95%EB%A0%AC