[Javascript(NodeJS)/Softeer] Lv3. 징검다리 (DP)

 

https://softeer.ai/practice/6293

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

---

소프티어 레벨 3.

대표적인 DP문제인 듯 하다!

크기 비교가 있기 때문에 꼭 꼭 배열을 Number로 바꿔줘야 한다 (이거때문에 첫 제출 틀림 ㅠㅡㅠ)

자스는 날 힘들게 해.....🫠

 

풀 때는 몰랐지만 LIS라는 문제 유형이라고 함!!

 

<< 최장 증가 부분 수열(LIS) 알고리즘>>

Longest Increasing Subsequence

: 주어진 수열에서 원소들의 순서를 유지하면서 가장 긴 증가하는 부분 수열을 찾는 알고리즘

 

n번째 인덱스 돌을 밟을 때, 난 어디서 왔나?를 생각하면 된다.

늘 그렇지만 dp는 코테에 나오면 항상 연습했던 것보다 훨씬 더 어렵다 ㅠㅠ

 

나의 풀이

const fs = require('fs');
const input = fs.readFileSync(0,'utf-8').trim().split('\n');

let n = Number(input[0].trim());
let heightList = input[1].trim().split(' ').map(Number);

// n번째 돌을 밟을 때 어디서 올 수 있는지 경우의 수
let dp = new Array(n).fill(1);
for(let i=0; i<n; ++i){
    let nownum = heightList[i];
    for(let j=0; j<i; ++j){
        if(nownum > heightList[j]) {
            dp[i] = Math.max(dp[j]+1, dp[i]);
        }
    }
}
console.log(Math.max(...dp));