[백준] 1548 부분 삼각 수열

문제

• 세 수 x, y, z가 다음과 같은 관계를 만족하면 삼각관계라고 말한다.
  x+y > z 이고 x+z > y 이고 y+z > x 이다.
• 마찬가지로 길이가 N인 수열 B의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 삼각수열이라고 한다.
• 수열 A가 주어졌을 때, 이 수열에서 적절히 몇 개의 원소를 빼서 이 수열을 삼각 수열로 만들려고 한다. 
• 삼각수열의 최대 길이 구하기

 

• 3 <= N <= 50
  1 <= 각 수열의 원소 <= 10^9
  
  
  

풀이

• 모든 수가 삼각관계를 만족하려면 수열의 가장 작은 두 수의 합이 가장 큰 수보다 커야한다.
• 수열을 정렬한 뒤, 앞 뒤로 움직여가며 가능한 가장 긴 길이 찾기 = 그리디

 

N = int(input())
sequence = list(map(int, input().split()))
sequence.sort()
answer = 1

for s in range(N-1) :
    for e in range(N-1, s, -1):
        if sequence[s]+sequence[s+1] > sequence[e] :
            answer = max(answer, e-s+1)

print(answer)

 

References

• 백준 오늘의 문제