백준 1548번: 부분 삼각 수열

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

문제 풀이

브루트 포스

arr = 오름차순으로 정렬한 수열

answer = 삼각 수열이 되는 최대 길이

i = 현재 삼각 수열을 검사하는 수열의 범위 중 최솟값의 인덱스

j = 현재 삼각 수열을 검사하는 수열의 범위 중 최댓값의 인덱스

삼각 수열의 정의가 원소 3개 이상일 때 서로 다른 수 세개를 뽑아 그 수에서 두개 쌍을 뽑으면 그 합이 다른 수보다 항상 커야 한다는 점이므로 원소 2개 이하라면 전제 조건이 거짓이라 무조건 참임

따라서 answer를 2와 N중 더 작은 값으로 초기화함

만약 answer와 N이 같으면 원소를 뺄 필요가 없으므로 바로 answer를 출력하면 됨

다르다면 원소를 제외하며 찾아야 하므로 i를 0부터 확인하며 현재 수열의 최솟값 2개인 arr[i], arr[i + 1]을 더한 값이 arr[j]보다 크게 되는 j를 arr의 뒤에서부터 찾아 그때의 길이 j - i + 1과 answer를 비교해 더 큰 값을 answer에 저장함

그렇게 i를 1씩 증가시키며 최대 길이를 찾다보면 이미 찾아놓은 길이 answer보다 현재 검사해야 하는 수열의 길이 j - i + 1이 더 작을 수 있음

그 경우 현재 수열의 범위는 원소를 제외해도 이미 찾은 최대 길이보다 무조건 작기 때문에 검사할 필요가 없으니 넘김

이에 따라 반복하다보면 최대 길이가 answer에 저장되므로 출력하면 정답

풀이 설명

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

이 문제의 조건대로 삼각 수열이 되려면 수열에서 제일 작은 두 값의 합이 수열에서 제일 큰 값보다 커야 한다.

따라서 주어진 수열을 삼각 수열이 되게 만드려면 오름차순으로 정렬한 후 삼각 수열의 조건에 맞도록 수열의 최솟값, 최댓값을 조절하며 삼각 수열이 되는 가장 긴 수열의 범위를 찾으면 된다.

문제를 풀기 위해 수열을 배열 arr에 저장하고 오름차순으로 정렬한 다음, 최솟값의 인덱스를 i, 최댓값의 인덱스를 j로 지정하고 삼각 수열이 되는 가장 긴 수열의 길이를 answer로 정의한다.

삼각 수열의 조건이 원소가 3개 이상일 때 두 수의 합이 다른 수보다 커야 하는 것인데, 원소가 2개 이하라면 전제 조건부터 거짓이 되므로 조건이 의미가 없어진다. 따라서 answer의 초깃값으로 N과 2 중 더 작은 값으로 초기화 하면 된다.

그 이후엔 i를 하나씩 증가시키면서 j를 끝에서부터 감소시키며 삼각 수열을 만족하는 최대 길이를 구하면 된다.

이때 i를 증가시킬때마다 검사하는 범위가 하나씩 줄어들고, 최대 길이를 찾는 것이므로 현재 검사하는 수열의 길이 j - i + 1이 answer보다 작으면 그 수열은 검사할 필요가 없어진다.

또한 최대 길이를 찾는 것이므로 j를 가장 끝인 최댓값의 인덱스부터 하나씩 줄여가며 삼각 수열을 이루는 첫 최댓값을 찾으면 그때의 길이만 확인하면 된다.

그러면 answer에 삼각 수열의 최대 길이가 저장되므로 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val N = nextInt()
    val arr = IntArray(N)
    for(i in 0 until N){
        arr[i] = nextInt()
    }
    arr.sort()
    var answer = minOf(2, N)
    if(answer != N){
        for(i in 0 until N - 2){
            var j = arr.size - 1
            if(j - i + 1 < answer) break
            while(j >= i + 2){
                if(arr[i] + arr[i + 1] > arr[j]){
                    answer = maxOf(answer, j - i + 1)
                    break
                }
                j--
            }
        }
    }
    println(answer)
}