백준 GOLD 5(전깃줄) - #2565

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2023-02-09

  • 해결 방법 :

    • dp를 활용해 문제 해결
    • A 전깃줄 오름차순 정렬
    • N^2번 반복하며 B 전깃줄에서 이전 위치의 값보다 클 경우(교차하지 않는 경우) dp 업데이트
    • N - dp의 최댓값 반환

  • 회고 :

    • 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 poles = props
    .slice(1)
    .map((prop) => prop.split(' ').map((e) => +e))
    .sort((a, b) => a[0] - b[0]);
  const dp = Array(N).fill(1);

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < i; j++) {
      if (poles[i][1] > poles[j][1]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  console.log(N - Math.max(...dp));
}

  • 출처: 백준