[Softeer/Javascript] 징검다리

알고리즘 : LIS (이분탐색)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = Number(input[0]);
const stones = input[1].split(' ').map(Number);

function bisect_left(arr, target) {
    let left = 0;
    let right = arr.length;

    while (left < right){
        const mid = Math.floor((left+ right)/ 2)
        if (arr[mid] < target){
            left = mid + 1
        }else {
            right = mid
        }
    }
    return left
}

const dp = [0];
for (let i = 0; i < n; i++) {
    const idx = bisect_left(dp, stones[i]);

    if (idx === dp.length) {
        dp.push(stones[i]);
    } else {
        dp[idx] = stones[i];
    }
}

console.log(dp.length - 1);

 

LIS 알고리즘을 알고 있다면 간단한 문제