-
백준 - 부분 삼각 수열
문제 설명 길이가 N인 배열이 주어진다. 삼각 수열의 최대 길이를 구하는 프로그램을 작성하시오. 삼각 수열이란 a[0], a[1] …. a[n-1]의 배열에서 b[i], b[j], b[k]가 삼각 관계에 있으면 삼각 수열이다. 삼각 관계는 세개의 수가 x+y>z, x+z>y, y+z>x 관게를 만족하는 관계이다. 문제이해가 중요하다. 원본 배열에서 일부를 뽑아 부분수열을 만들고 삼각 부분 수열의 최대길이를 구하는 문제이다. 삼각 관계를 보면 세 수를 정하고 세수가 위 조건의 상하 관계를 만족하는 것을 볼때, b[k]는 가장 큰 숫자이고 b[i]는 가장 작은 숫자로 본다. 이를 보면 정렬이 생각나야 된다. n=7, arr[]=[2,3,4,1,3,4,5] 일때, 답은 5가 나온다. 만약 중간에 다른 수들이 ..
Algorithm/백준
2023. 4. 4.
