글 읽기 - 2565 LIS로 풀었는데 반례를 못찾겠습니다.

zzalsrud 2년 전 0

왼쪽 전봇대 번호 기준으로 정렬해서 오른쪽 전봇대 번호를 가지고 LIS 해서 전체 전깃줄 개수 - LIS 최댓값 했는데 시작하자마자 틀렸습니다 뜨네요 ㅠㅠ

게시판의 반례들 다 해봤는데 잘 됐는데 뭐가 문제일까요?

let fs = require("fs");
let flex = fs.readFileSync("/dev/stdin").toString().split("\n");
const N = Number(flex[0]);
flex.shift();
flex = flex
  .map((element) =>
    element
      .trim()
      .split(" ")
      .map((element) => Number(element))
  )
  .sort((a, b) => a[0] - b[0]);
const dp = new Array(N);
dp[0] = 1;
for (let i = 1; i < N; i++) {
  const value = [1];
  for (let j = 0; j < i; j++) {
    if (flex[i][1] > flex[j][1]) {
      value.push(dp[j] + 1);
    }
  }
  dp[i] = Math.max(...value);
}

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

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2565 LIS로 풀었는데 반례를 못찾겠습니다.

zzalsrud 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말