[BOJ1548 - Python] 부분 삼각 수열

문제

---

1548번: 부분 삼각 수열

 

세 수 x, y, z에 대하여 x+y>z, x+z>y, y+z>x의 관계를 만족할 경우, 세 수는 삼각관계에 있다고 한다.

즉, 세 수 중 가장 큰 수를 z라고 할 경우 x+y>z를 만족하면 삼각관계인 것이다.

 

길이가 N인 수열 B(b[0], b[1], ... , b[n-1])에서

모든 b[i], b[j], b[k]가 삼각관계에 있다면 이 수열은 삼각 수열이라고 한다. (i, j, k는 모두 다른 값)

 

입력으로 수열이 주어졌을 때 이 수열을 통해 만들 수 있는 삼각 수열의 최대 길이를 구하는 것이 문제이다.

 

 

풀이

---

문제를 읽었을 때 수열에서 i, j, k는 모두 다른 값이라고 명시를 했기 때문에

삼각 수열의 길이는 무조건 3 이상이겠구나~ 생각했지만 예제를 보니

 

띠용

 

띠용 2

 

예제 1의 답이 2라면

1, 2, 3으로 만들 수 있는 최대 길이의 삼각 수열은 2, 3이 된다는 것이고 (2+2>3)

 

예제 5의 답이 1이라면

최대 길이의 삼각 수열이 1이라는 것인데.. (1+1>1)

 

문제에 수열의 길이가 2 이하일 경우의 처리는 어떻게 해야 하는 것인지에 대한 설명이 더 있었으면 좋았을 것 같다.

일단 입력받은 수열의 크기 N이 3 미만일 경우, 바로 N을 결과로 출력하는 것으로 구현하였다.

---

N이 3 이상일 경우 문제 풀이를 위한 로직은 다음과 같다.

 

1. 입력 받은 수열(numList)을 오름차순으로 정렬한다.

 

2. x, y, z라는 세 변수에 numList에 저장되어 있는 각각 다른 값을 담아 이것이 삼각 수열인지 판단할 것인데, x < y < z가 되도록 값을 담을 것이다.

x, y, z가 삼각 수열을 만족할 경우 해당 삼각 수열의 길이는 (x와 z 사이의 거리 + 1)이다.

 

x와 y에는 서로 인접하는 값들을 저장해주고, z는 수열의 맨 마지막 값부터 시작한다.

 

 

x, y, z가 삼각 수열을 만족할 경우 최대 삼각 수열의 길이를 담는 변수(result)에 저장(정확히는 현재 result에 담겨있는 값과 방금 구한 삼각 수열의 길이 중에서 더 긴 값을 저장)하고,

 

만족하지 않았을 경우 z의 위치를 한 칸 앞으로 당겨 다시 삼각 수열인지를 확인하는데

이것은 삼각 수열을 계속 찾지 못하여 z가 y의 값에까지 도달하였을 경우까지 반복된다.

 

(1) 삼각 수열을 찾았을 경우 또는 (2) z가 y의 값에 도달한 경우

x와 y를 한 칸 전진하여 바꾸고, z는 다시 수열의 맨 마지막 값으로 돌아가 위를 계속 반복한다.

 

 

 

코드

---

import sys

N = int(sys.stdin.readline().strip())
numList = list(map(int, sys.stdin.readline().split()))

result = 0

if N < 3:  # 숫자의 개수가 3 미만인 경우 -> N 반환
    result = N

else:
    numList.sort()  # 오름차순 정렬

    for i in range(N - 1):
        x = numList[i]
        y = numList[i + 1]

        for j in range(1, N):
            z = numList[-j]

            if x + y > z:
                result = max(result, N - j - i + 1)
                break
            elif y == z:
                break

print(result)