[백준] 1548 부분 삼각 수열 (Javascript)

문제

BOJ1548 부분 삼각 수열

문제 정리

우선 문제 이해부터 어려웠다.
문제를 정리해보면 우선 삼각 수열이란 수열 b가 있을 때

1. b[i] + b[j] > b[k]
2. b[i] + b[k] > b[j]
3. b[j] + b[k] > b[i]

위 세 조건을 만족해야 한다. 그리고 이때 i,j,k는 모두 다른 값이다.

수열이 주어졌을 때 원소를 적절히 빼서 이 수열을 삼각수열로 만들어서 삼각 수열의 최대 길이를 구해야 한다.

이해 과정

아직 무슨 얘긴지 제대로 이해가 안돼서 예제를 보았다.
근데 예제 1번을 보니 더 혼란스러웠다.
수열 1 2 3 일때 삼각수열의 길이가 어떻게 2인거지? 라는 의문이 들었다.

수열 1 2 3은 아래 세 조건을 모두 만족하지 못하기 때문에 삼각 수열이 아니다.

1. 1 + 2 > 3 // false
2. 1 + 3 > 2 // true
3. 2 + 3 > 1 // true

이 상태로 삼각 수열을 만들기 위해 수열에서 원소를 빼면 원소가 3개 미만이 되니 삼각 수열의 조건을 사용할 수 없다.

"따라서 삼각 수열의 최대 길이는 0이 나와야 하지 않나?"가 나의 생각이었다.

이와 비슷한 질문이 질문 게시판에 있었다.

https://www.acmicpc.net/board/view/86970

하지만 답변을 봐도 이해가 되지 않았다.
그래서 Chat GPT의 도움을 받아 아래와 같이 이해했다.

1. "삼각수열"이란 수열 B에 대해 모든 서로 다른 세 원소 $b[i], b[j], b[k]$가 삼각관계를 만족하면 해당 수열을 삼각수열이라고 한다.
2. 수열의 길이가 3 미만이면 서로 다른 세 원소 $b[i], b[j], b[k]$를 고를 수 없다.
3. $N \lt 3$인 $i,j,k$와 같이 서로 다른 세 원소를 선택할 수 없기 때문에, 삼각 수열의 조건인 "모든 서로 다른 세 원소가 삼각 조건에 만족해야한다"는 명제가 적용되지 않는다.
4. 서로 다른 세 원소 $i,j,k$를 선택할 수 없다는 것은 삼각 수열의 조건을 적용할 수 없기에 "조건을 위반하는 경우가 없다"고 해석할 수 있고, 따라서 자동으로 삼각 수열의 조건을 만족한다고 볼 수 있다.

따라서 $N<3$인 경우는 삼각 수열이 되므로 예제 1번에서 1 2 3은 삼각수열이 될 수 없기 때문에 원소를 하나 제거해서 길이 2의 수열이 되고, $2<3$이기 때문에 삼각 수열이다. 따라서 가장 긴 삼각수열이 2가 되는 것이다.

접근법

문제 이해부터 실패했기 때문에 다른 분의 풀이를 참고했다.

$b[i], b[j], b[k]$가 삼각관계인지 확인하려면 $b[i] \le b[j] \le b[k]$ 일때, $b[i] + b[j] \gt b[k]$를 만족하는지 확인하면 된다.

$b[i] \le b[j] \le b[k]$ 라면 $b[i],b[j],b[k]$가 0이 아닌 양수인 이상 아래 조건중 2번과 3번은 자동으로 만족하기 때문에 1번 조건만 확인해주면 되기 때문이다.

1. $b[i] + b[j] \gt b[k]$
2. $b[i] + b[k] \gt b[j]$
3. $b[j] + b[k] \gt b[i]$

따라서 $b[i] \le b[j] \le b[k]$ 조건을 만들어주기 위해 수열 B를 오름차순으로 정렬한다.
그리고 $j = i+1$, $k = j+1$이상이라면 $b[i] \le b[j] \le b[k]$가 만족할 것이다.

만약 길이가 $N$인 수열이 있고 i = 0, j = 1, k = n-1이라고 했을 때, $b[0] + b[1] \gt b[N-1]$ 이 true라면 k가 2~n-2일 때를 굳이 확인해보지 않아도 true라는 것을 알 수 있다. ($k$가 작아질수록 $b[k]$의 값도 작아지기 때문)

따라서 $j$는 $i+1$로 설정하고 $k$를 $N-1$부터 1씩 감소시켜주다가 조건이 참인 경우를 발견하면 그대로 반복을 중지시켜주면 된다. 이는 수열에서 가장 작은 두 값 $b[i], b[j]$를 더했을 때 수열에서 가장 큰 값인 $b[k]$를 초과하는 것이므로 $b[i] \sim b[k]$는 삼각수열임을 의미한다. 따라서 이때의 수열의 길이중 가장 긴 수열이 정답이 된다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');

const N = +input[0];
const nums = input[1].split(' ').map(Number);

let result = 0;
nums.sort((a, b) => a - b);

for (let i = 0; i < N - 1; i++) {
    let j = i + 1;
    for (let k = N - 1; k >= 0; k--) {
        if (j === k) break;
        if (nums[i] + nums[j] > nums[k]) {
            result = Math.max(result, k - i + 1);
            break;
        }
    }
}

if (result === 0) {
    result = N >= 2 ? 2 : N;
}

console.log(result);