[백준] 1548 부분 삼각 수열 java

문제

세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다.

마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 수열이라고 한다. 이때, i, j, k는 모두 다른 값이다.

수열 A가 주어졌을 때, 이 수열에서 적절히 몇 개의 원소를 빼서 이 수열을 삼각 수열로 만들려고 한다. 삼각 수열의 최대 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. 둘째 줄에 수열 A에 들어있는 수가 공백을 사이에 두고 주어진다. N은 최대 50이고, A에 들어있는 수는 109보다 작거나 같은 자연수이다.

출력

첫째 줄에 가장 긴 부분 삼각 수열의 길이를 출력한다.

풀이

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int n, maxLen;
    static int[] a;

    public static void main(String[] args) throws IOException {
        init();
        solve();
        if(maxLen != Integer.MIN_VALUE) {
            System.out.println(maxLen);
        } else {
            System.out.println(2);
        }
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = stoi(br.readLine());
        a = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            a[i] = stoi(st.nextToken());
        }
        Arrays.sort(a);
        maxLen = Integer.MIN_VALUE;
    }

    static void solve() {
        if(n < 3) {
            maxLen = n;
            return;
        }
        for(int i = 0; i < n-3; i++) {
            int sum = a[i] + a[i+1];
            for(int j = n-1; j >= i+2; j--) {
                if(sum > a[j]) {
                    maxLen = Math.max(maxLen, j-i+1);
                    break;
                }
            }
        }
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

그리디 + 완전탐색 문제이다.

 

주어진 A 수열에서 부분 수열의 I, J, K가 삼각관계가 성립하는 모든 부분 수열을 찾아 MAX 길이를 갱신해주면 된다.

하지만 그냥 찾으면 일일히 전부 비교햐줘야 하니 우선 최적화 시킬 수 있는 부분부터 찾아보자.

 

수열의 각 원소는 순서가 상관이 없으니 정렬을 해준다. 그렇게 되면 A[0]+A[1] > A[N-1]이 성립되는지만 알면된다. 만약 이것이 성립한다면 이미 정렬된 상태이기 때문에 그 이하의 수들도 삼각관계가 성립된다는 뜻이다. 그러니 부분 삼각 수열이 성립된다면 현재 MAX 길이와 비교해서 갱신해주면 된다.

 

만약 성립하지 않는다면 N-1 부터 하나씩 빼가면서 A[2] 까지 비교해 나가면 된다. 

그리고 모든 부분수열을 고려해야 하기 때문에 길이가 3 이상인 수열에서 최소 A[0]부터 A[N-3]까진 비교해줘야 한다. 

 

ex) N = 6

1 1 1 100 100 100

0번째 인덱스의 부분 삼각 수열 = 3 (0, 1, 2)

1번째 인덱스의 부분 삼각 수열 = 2 (성립 X 최소 길이)

2번째 인덱스의 부분 삼각 수열 = 4 (2, 3, 4, 5)

3번째 인덱스의 부분 삼각 수열 = 3 (3, 4, 5)