백준 1448. 삼각형 만들기

문제 링크

난이도	정답률(_%)
Silver 3	45.445%

설계

• 총 빨대의 개수 N 1,000,000
• 처음엔 완탐을 생각했는데 빨대의 개수가 너무 많아서 불가능하다고 판단했다.
• 그러다 정렬해서 뒤부터 찾으면 어떨까라고 생각했고, 삼각형의 조건(가장 긴변 < 나머지 변의 합)을 생각해보니 순서대로 3개가 삼각형에 성립하지 않았다면 그 이하의 변의 조합에서는 성립할 수 없기 때문에 나머지 2개 변의 조합은 탐색할 필요가 없다는 것을 알았다.

예를 들어 빨대가 5개가 있을 때, index (5, 4, 3)이 삼각형 조건에 성립하지 않았다면 index (5, 4, 2)는 성립할 수 없다. 정렬된 상태이기 때문에 index 2가 index 3보다는 값이 작거나 같을 수 밖에 없기 때문이다.

시간 복잡도

• 정렬: O(NlogN)
• 탐색: O(N)
• O(NlogN) + O(N)..?

공간 복잡도

• 빨대의 개수 만큼 int형 배열 O(N)

풀이

• 빨대들의 길이를 정렬한다.
• 뒤부터 순서대로 i, i-1, i-2를 뽑아서 삼각형이 되면 그 총 합을 출력, 끝까지 찾지 못하면 -1을 출력한다.

코드

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

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

        int strawNumber = Integer.parseInt(br.readLine());
        int[] straws = new int[strawNumber];

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

        bw.write(String.valueOf(findMaxTriangle(strawNumber, straws)));

        bw.flush();
        bw.close();
    }

    public static int findMaxTriangle(int strawNumber, int[] straws) {
        Arrays.sort(straws);

        for (int i = strawNumber - 1; i > 1; i--) {
            if (canTriangle(straws[i], straws[i - 1], straws[i - 2])) {
                return straws[i] + straws[i - 1] + straws[i - 2];
            }
        }

        return -1;
    }

    public static boolean canTriangle(int a, int b, int c) {
        if (a < b + c) {
            return true;
        }

        return false;
    }
}