[BOJ - JAVA] 1548 - 부분 삼각 수열(브루트포스)

# 주소

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

1548번: 부분 삼각 수열

# 문제

# 문제 해설 및 코드 리뷰

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n;
    static int[] arr;
    static int min = 1;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        Arrays.sort(arr);
        if (n > 2) {
            for (int i = 0; i < n - 1; i++) {
                for (int j = n - 1; j >= 0; j--) {
                    if (i + 1 == j)
                        break;
                    if (arr[i] + arr[i + 1] > arr[j]) {
                        min = Math.max(min, j - i + 1);
                        break;
                    }
                }
            }
        }
        // 1 2 3 4 5
        if(min == 1 && n >= 2)
            min = 2;
        System.out.println(min);
    }
}

처음에 백트래킹으로 풀려고 했는데 돌이켜 생각해보니 이 문제에서 얘기하는 길이가 무엇을 의미하는지 도통 감을 못잡았었습니다.

문제에서 만약 입력문이 

3
1 2 3

이렇게 되었다면 출력이 2가 나온다고 했는데, 삼각 수열인데 도대체 왜 숫자를 3개 비교 하지 않고 2개만 비교하는건지... 한참을 고민했습니다.

심지어 맞춘사람이 100명이 안되어서 검색해도 안나옵니다 ㅋㅋㅋ

쭉 고민을 한 결과 문제에서 이야기하는 최대 길이는 실제 인덱스의 길이를 의미하는 것이 아니고, 수열에서 가질 수 있는, 나타낼 수 있는 인덱스의 길이를 의미하는 것이었습니다.

 

예를 들어 예제처럼

7
2 3 4 1 3 4 5

이렇게 입력되었을 경우 이를 오름차순으로 정렬하면

1 2 3 3 4 4 5가 되게 만들어서 이 때 부분 삼각수열이 될 수 있는 수열의 최대 길이를 찾으란 것입니다.

결과적으로 2 3 4가 선택되어 최대 길이는 5가 될 것입니다. (2번째와 3번재 인덱스와 6번째 인덱스까지의 길이)

 6 - 2 + 1 = 5이기 때문입니다.

코드로 살펴봅시다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
    arr[i] = scan.nextInt();
}

n과 arr를 먼저 입력받습니다.

그리고

Arrays.sort(arr);

arr를 오름차순으로 정렬합니다.

if (n > 2) {
            for (int i = 0; i < n - 1; i++) {
                for (int j = n - 1; j >= 0; j--) {
                    if (i + 1 == j)
                        break;
                    // 1 2 3 3 4 4 5
                    if (arr[i] + arr[i + 1] > arr[j]) {
                        min = Math.max(min, j - i + 1);
                        break;
                    }
                }
            }
        }

그리고 n이 2보다 크다면 이중 for문으로 탐색할 것인데, i는 0부터 n-1까지 탐색할 것입니다.

왜냐하면 arr[i] + arr[i+1]을 탐색하기 위함입니다.

또한 2번째 for문 부터는 j = n-1부터 0까지 탐색할 것입니다.

그리하여 j는 내림차순으로, i는 오름차순으로 탐색할 것입니다.

여기서 주목할 것이, i는 왼쪽에서부터 그리고 j는 오른쪽에서부터 다가오는 투 포인터 방식이기 때문에 결과적으로 만약 i + 1 == j 가 되면 같은 값을 비교해버리는 상황이 되기 때문에 문제의 조건인 서로 다른 세 수의 규칙에 위배됩니다.

그러므로 i + 1 == j가 되면 break;하여 for문을 빠져나오도록 하겠습니다.

그리고 만약 arr[i] + arr[i+1] > arr[j]면 min값에 담을 것입니다.

그런데 이 때 min에 들어갈 크기는 j - i + 1입니다.

수학을 조금 해보신 분들은 바로 이해할 거에요.

예를 들어 2 <= x <= 10이면 이걸 만족하는 자연수 x는 몇개지요?

9개잖아요? 그건 어떻게 도출되었나요?

10 - 2 + 1해주었죠? 

크거나 같다는 부등호가 있다면 +1해주고 둘다 그렇지 않을 경우는 -1, 그리고 하나만 있다면 그대로 해주는 것이 규칙입니다.

자 이렇게 min을 계속 갱신하여 출력해보면 정상적으로 출력되는 것을 알 수 있습니다.

만약 n이 2보다 크거나 같은데 min이 1이라면 그냥 2로 출력해야 정답이 됩니다.

이건 설명이 조금 부실하다 생각이 드네요...

감사합니다.