[백준] 부분 삼각 수열

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

1548번: 부분 삼각 수열

1. 문제 이해

수열이 주어지고 수열에 포함된 숫자 중 3개를 뽑았을 때 x+y>z, x+z>y, y+z>x를 만족하는 가장 긴 수열을 찾는 문제입니다. 단, 숫자를 원하는대로 삭제할 수 있습니다.

2. 문제 접근

수열을 선택했을 때, 가장 작은 두 숫자의 합이 수열에서 가장 큰 수보다 커야합니다. 따라서, 수열을 정렬하고 가장 작은 두 숫자의 합이 수열의 가장 큰 수보다 클 때 부분 삼각 수열을 완성할 수 있습니다. 더이상 삼각 수열을 만족하지 못하면 가장 작은 두 숫자를 갱신해주면 됩니다 .

3. 풀이

import sys

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))

nums.sort()

left, right = 0, 0

ans = 0
while right < n:
    while right - left + 1 >= 3 and nums[left] + nums[left + 1] <= nums[right]:
        left += 1
        continue
    ans = max(ans, right - left + 1)
    right += 1
print(ans)

 

수열을 정렬한 투 포인터를 사용하여 수열의 길이가 3이 넘어가면 가장 작은 두 숫자의 합이 수열에서 가장 큰 숫자보다 작은지 체크하고 작게 되면 left를 증가시켜 가장 작은 두 숫자를 갱신해주면 됩니다.