[백준] 1548 부분 삼각 수열

백준 1548 부분 삼각 수열

길이가 N인 수열이 주어졌을 때, 적절히 몇 개의 원소를 제거하여 삼각 수열을 만들고, 그중 가장 긴 부분 삼각 수열의 길이를 구하는 문제이다.
즉, 주어진 수열에서 일부 숫자를 골라 삼각 관계를 만족하는 가장 긴 부분 수열을 찾는 것이 목표이다.

문제 해결 접근

1. 완탐의 어려움
   • 길이가 최대 500인 배열에서 모든 조합을 확인하면 시간 초과가 남
2. 정렬을 활용한 최적화
   • "모든" 원소가 삼각 수열 조건을 만족해야 하는데 가장 중요한 포인트는 수열 내에 가장 작은 두 수의 합이 가장 큰 원소보다 작아야 한다는 점이고, pop method와 같이 배열을 수정할 필요가 없다는 점이다.
   • 따라서 수열을 정렬하고, 투 포인터 방식으로 가장 긴 부분 삼각 수열을 찾는 방법을 고려하면 된다

import sys

def solution():
    inp = sys.stdin.readline
    int(inp())
    arr = list(map(int, inp().split()))
    arr.sort()  # 정렬을 수행하여 작은 수부터 고려
    
    res = min(2, len(arr))  # 기본적으로 길이는 최소 2 (최소한 두 개의 수는 선택 가능)
    
    for i in range(len(arr) - 2):  # 첫 번째 원소 고정
        for j in range(i + 2, len(arr)):  # 세 번째 원소를 선택
            if arr[i] + arr[i + 1] > arr[j]:  # 삼각 수열 조건 확인
                res = max(res, j - i + 1)  # 최대 길이 갱신
    
    print(res)

if __name__ == "__main__":
    solution()

코드 설명

1. 수열 정렬
   삼각 수열을 만들기 위해서는 정렬된 상태에서 숫자들을 선택하는 것이 유리하다.
   최소 길이 설정

2. 최소 길이 설정
   수열 길이가 2 이하라면 삼각 수열을 만들 수 없다는 것과, 배열의 길이가 1인 경우를 고려

3. 투 포인터를 활용한 탐색
   i를 첫 번째 원소로 고정하고, j를 세 번째 원소로 설정하여 가능한 가장 긴 삼각 수열을 찾는다.
   arr[i] + arr[i+1] > arr[j] 조건을 만족하는 경우, 가능한 부분 수열의 길이를 갱신한다.