[백준 1548번] 부분 삼각 수열(파이썬)

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

1548번: 부분 삼각 수열

이 문제는 처음 문제를 읽다가

이게 뭔소리야?

하면서 이해를 못했던 문제.

1번 예시에서 

최대길이를 2라고 출력했습니다.

어라? 삼각수열은 분명

3개가 들어가야하니깐

최소 3이 되어야할텐데.

이게 뭐지?

구글링해서 뒤지다가

배열이 2보다 큰데

삼각수열이 0이라면

저렇게 받아도 되는 걸 알게되었습니다.

 

이 문제에서 오랫동안 헤맸던 건

'수열을 만든다'라는 것입니다.

배열을 정렬한 다음에

문제의 조건에 따라 배열을 넣었습니다.

처음에는 

num[x]+num[y]>num[z]라면

집합에

x,y,z를 넣는 식으로 했죠.

(집합을 쓰는 건 중복을 없애기 위함)

그랬더니 예제2에서 문제가 생겼습니다.

예제2같은 경우에는 그렇게 했다가

모든 걸 다 받아버렸죠.

이건 내가 원하는게 아닌데...

결국 집합에 num[x],num[y],num[z]

이렇게 넣는 식으로 했더니

예제3같은 경우에는

중복이 없어서 1로 받았습니다.

흐음...이거 뭔가 이상한데.

대체 어떻게 받아야하지...

 

한참을 고민하다가 구글링한 결과

'범위'라는 힌트를 얻었습니다.

즉, x와 z의 범위를 구하고

이게 최대가 되는 값을 찾는 식으로요

#백준 1548 부분삼각수열

N=int(input())

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

answer=1

for x in range(N-1):
    for z in range(N-1,-1,-1):
            if z<x+1:
                continue
            if nums[x]+nums[x+1]>nums[z]:
                answer=max(z-x+1,answer)



print(answer)

 

이 문제에서 수열을 리스트로 넣을까

집합으로 넣을까 고민했지만

결국 답은 범위였습니다.

이 문제를 통해

범위로 값을 넣는 아이디어를 얻게 되었습니다.