백준 - 부분 삼각 수열

문제 설명

길이가 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가 나온다.
  • 만약 중간에 다른 수들이 있게 되면 삼각 부분수열을 유지할 수 없다.
  • 1,2, 3,3,4,4,5
    • [3,3,5]도 조건 만족
    • [3,4,5]도 조건 만족
    • [4,4,5]도 조건을 만족한다.
  • 만약 정렬을 하지 않는다면 [3,4,1,2,3,4,5] 배열에서 최대 길이는 7이나와 오답이 된다.
• 여기에서 배열의 길이가 3미만일 때는 자동으로 만족한다.글 읽기 - 정답은 맞았습니다만 지문 관련해서 질문이 있습니다.
• N<3이면 i<j<k인 i,j,k가 없으니, i<j<k인 쌍에 대한 모든 명제를 자동으로 만족합니다.

풀이

public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(reader.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);
		int maxLength = Math.min(n, 2);

		for (int first = 0; first < n - 1; first++) {
			for (int third = n - 1; third >= 0; third--) {
				if (first + 1 == third) // 서로 다른 세 수가 아니다! (조건 만족 x)
					break;

				int firstNext = first + 1;
				if (arr[first] + arr[firstNext] > arr[third]) { // 삼각 수열을 만족한다면
					maxLength = Math.max(maxLength, third - first + 1);
					break; // 왜 =: 어차피 최대 길이를 구하므로 전에는 어차피 짧다.
				}
			}
		}

		System.out.println(maxLength);
	}