[boj] 백준 1548 부분 삼각 수열 (Java) - 완전탐색

[문제]

https://www.acmicpc.net/problem/1548

1548번: 부분 삼각 수열

 

[풀이]

먼저 삼각관계를 이루기 위해서는 오름차순으로 정렬했을 때 인덱스가 0, 1, ...., k 에 대해서 arr[0]+arr[1] > arr[k] 를 만족해야 한다. 가장 작은 두 수의 합이 가장 큰 수보다 크다면 세 수 x, y, z에 대해서 x+y>z, x+z>y, y+z>x의 관계를 만족할 것이기 때문이다.

따라서 i, j, k에 대해서 i와 j를 작은 두 수로 선정하고 j값을 키워가며 부분 삼각 수열의 최대 길이를 구한다.

 

[코드]

 

package 브루트포스;

import java.io.*;
import java.util.*;

public class boj_1548_부분삼각수열 {
    static int n;
    static int[] arr;
    static int answer = Integer.MIN_VALUE;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //삼각 수열의 최대 길이를 구하는 프로그램을 작성하시오.

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

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

        if(n==1 || n==2){
            System.out.println(n);
            return;
        }

        Arrays.sort(arr);

        int len = 2;
        for(int i=0; i<n-2; i++){
            len = 2;
            for(int j=i+2; j<n; j++){
                if(arr[i]+arr[i+1] > arr[j]){
                    len++;
                }
                else{
                    break;
                }
            }
            answer = Math.max(answer, len);
        }

        System.out.println(answer);

    }
    
}