알고리즘 문제 풀이(백준 - 가장 긴 증가하는 부분 수열 4)

백준 GOLD 4(가장 긴 증가하는 부분 수열 4)

• 사용 언어 : javascript

• 해결 날짜 : 2023-02-07

• 해결 방법 :

  • dp를 활용해 문제 해결
  • dp에 각 인덱스 별 증가하는 부분 수열 길이의 최대값 저장
  • 가장 긴 최대값을 저장 후(max)
    • dp를 역순으로 돌며 dp의 값과 같을 때 result에 push 및 max값 감소

• 회고 :

  • x

• 코드

  const fs = require('fs');
  const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
  const input = fs.readFileSync(filePath).toString().trim();
  
  solution(input);
  
  function solution(props) {
    props = props.split('\n');
    const N = +props[0];
    const numbers = props.slice(1).map((prop) => prop.split(' ').map((e) => +e))[0];
    const dp = Array.from({ length: N }, () => 1);
  
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < i; j++) {
        if (numbers[i] > numbers[j]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
    }
  
    let max = Math.max(...dp);
    console.log(max);
    const result = [];
  
    for (let i = N - 1; i >= 0; i--) {
      if (dp[i] === max) {
        result.push(numbers[i]);
        max--;
      }
    }
  
    console.log(result.reverse().join(' '));
  }
  

• 출처: 백준