문제 바로가기
문제:
세 수 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보다 작거나 같은 자연수이다.
출력:
첫째 줄에 가장 긴 부분 삼각 수열의 길이를 출력한다.
풀이:
길이가 2 이하이면 항상 삼각 수열이다
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n =int(input())
lst = sorted(list(map(int,sys.stdin.readline().split())))
res = 1
for i in range(n-1):
for j in range(n-1,-1,-1):
if j >= i+1 and lst[i] + lst[i+1] > lst[j]:
res = max(res,j-i+1)
print(res)
은은하게 쉬웠다.
처음에는 combinations 를 사용하려고 했지만, 시작 값에 따른 max값 갱신하는게 불가능하다.
x+y>z, x+z>y, y+z>x
즉 가장 작은 두 개의 수열의 합이 z보다 클때까지 비교하면 된다. z값만 알면 그 사이의 값은 정렬이 되어 있기때문에 다 가능하다.
예를들어
2,3,3,3,3,3,3,4,5 일때
23~~4 는 가능하지만, 23~~5 는 불가능하다 그래서 시작 값과 끝 값만 알면된다
포문에서 i는 시작하는 수열을 가르키고 j는 끝 수열을 말한다.
끝 수열은 i보다 커야 하므로 j+1 을 붙여줘야한다. 안 그러면 i 가 커진다.
예를들어 2,3,5 일때 i가 3이고 j가 2인 경우는 안된다.
댓글