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

문제링크

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

1548번: 부분 삼각 수열

---

 

코드

n = int(input())
data = sorted(list(map(int,input().split())))
if n>2:
    result = 2
    for start in range(n-2):
        end = start+2
        while True:
            if data[start] + data[start+1] > data[end]:
                result = max(result, end-start+1)
                end+=1
                if end==n:break
            else:break
    print(result)
else:print(n)

---

문제풀이

 

세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다.

만약 세 수가 있다면 작은수 + 그다음작은수 > 가장큰수 관계를 만족하면 삼각관계를 만족시킬 수 있다.

예를 들어 3,4,5가 있으면 3+4>5가 만족되면 3+5>4, 4+5>3은 자연스레 만족된다는 것을 알 수 있다.

따라서, 정렬을 한 후 가장 작은 두 수를 잡은 후 그 보다 큰 수를 비교해가며 삼각관계가 만족되는지 확인한다.

만족이 되면 큰 수를 계속 증가시켜가며 더 긴 삼각수열을 찾아가면 되고

만족이 되지 않는다면 그 이후의 수는 비교할 필요가 없다. 그 후 작은수를 증가시켜준다.

예를 들어 3,3,4,5,6,7 이 있다고 하면, 3+3>4, 3+3>5까지 만족하고 3+3>6 은 만족하지 않기 때문에 그 뒤에있는 3+3>7은 당연히 만족하지 않는다. 이 후 작은 두 수를 증가시켜 3+4>5, 3+4>6 이렇게 비교해나가면 된다.

예제 입력1과 예제 입력 5의 출력값이 이해가 가지 않았는데 길이가 2 이하이면 항상 삼각 수열이라고 한다.