[Softeer] 징검다리

https://softeer.ai/practice/6293

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

문제 정의가 그렇게 많지 않아 쉬운 문제인 줄 알았으나 생각보다 애를 먹인 문제임

 

주어진 배열에서 철수가 점점 더 높은 돌을 밟아야 함. 그래서 이중 반복문을 통해 시작 지점을 옮기며 계산했지만 예외가 있음

 

gpt의 도움을 통해 문제를 이해함. 해당 문제는 dp 문제로 dp의 배열에는 해당 인덱스까지의 최대 밟은 개수를 저장함

 

이중 반복문을 통해 현재 인덱스의 값보다 작은 값이 있으면 dp 배열을 통해 현재 dp값과 작은 값의 dp값에 + 1 한 값과 비교하여 저장함

 

현재 높이의 돌을 밟는다는 것은 이전 인덱스 높이가 현재 높이보다 낮다는 것임. 따라서 현재 인덱스까지 반복문을 돌면서 확인하여 최댓값을 저장하는 것임

 

dp 문제 접근 시 부분 문제를 어떻게 정의할 지에 대해서 연습이 더 필요함

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];

rl.on('line', (line) => {
     lines.push(line.trim());
}).on('close', () => {
    let answer = 0;
    const [cnt, strList] =  lines;
    const stoneList = strList.split(" ").map(it => +it);

    const dp = Array.from(Array(stoneList.length), () => 1);
    
    for(let i = 0; i < cnt; i++){
        for(let j = 0; j < i; j++){
            if(stoneList[j] < stoneList[i]){
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        answer = Math.max(answer, dp[i]);
    }

    console.log(answer);

    process.exit(0);
});