[BOJ/Python] 백준 1548 - 부분 삼각 수열

문제

문제

세 수 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보다 작거나 같은 자연수이다.

 

출력

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

풀이

n = int(input())
li = sorted(list(map(int,input().split())))

if n > 2:
    ans = 2
    for i in range(n - 2):
        end = i + 2
        while True:
            # 정렬했을 때 앞의 작은 수 두 개의 합이 더 크면 중간 수도 조건 다 만족
            if li[i] + li[i + 1] > li[end]:
                ans = max(ans, end - i + 1)
                end += 1
                if end == n:
                    break
            else:
                break
    print(ans)
# 예제 1, 5의 경우, 삼각 수열을 이루는 수열의 원소가 3보다 작으면 그냥 원소의 개수 반환
else:
    print(n)

 

• 예제 1, 5 출력 내용이 1도 이해가 안됐다.. 삼각 수열을 이루는 원소가 3보다 작으면 원소의 개수를 반환한 것 같다
• 몇 개의 원소를 빼서 수열을 만든다는 게 주어진 순서에서 몇 개만 빼는 게 아니었다
• 리스트를 순서대로 정렬해서, 앞의 수 2개의 합이 다음 수보다 더 크면 조건을 만족하므로, while 문을 돌면서 end를 하나씩 늘린다
• 조건을 만족하지 않으면, 다음 시작점으로 넘어간다.