https://www.acmicpc.net/problem/2565
📌 작성한 코드
// 2565
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const N = Number(input.shift());
const list = input.map((str) => str.split(" ").map(Number)).sort((a, b) => a[0] - b[0]);
const lines = list.map(([_, val]) => val);
// 가장 긴 증가하는 부분 수열의 길이 구하기
// dp[i] = i를 마지막 값으로 가지는 증가 수열의 길이
const dp = Array(N).fill(0);
for (let i = 0; i < N; i++) {
dp[i] = 1;
for (let j = 0; j < i; j++) {
if (lines[i] > lines[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
console.log(N - Math.max(...dp));
📌 설명
1. 전깃줄을 입력받은 후에 전깃줄의 시작점(왼쪽)을 기준으로 오름차순 정렬한다.
2. 전깃줄의 끝점을 기준으로 보았을 때 가장 긴 증가하는 수열의 길이를 구하면 교차하지 않고 남아있을 수 있는 최대 전깃줄의 개수를 구할 수 있다.
3. 남아있을 수 있는 전깃줄의 개수를 구했으니 총 전깃줄의 개수에서 해당 개수를 빼주면 원하는 제거해야 하는 최소 전깃줄의 개수를 구할 수 있다.

✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/DP] 백준 골드 3 : 11066 - 파일 합치기 (0) | 2024.05.22 |
|---|---|
| [JavaScript/DP] 백준 골드 4 : 11054 - 가장 긴 바이토닉 부분 수열 (2) | 2024.05.21 |
| [JavaScript/DP] 백준 골드 4 : 1633 - 최고의 팀 만들기 (0) | 2024.05.15 |
| [JavaScript/DFS/DP] 백준 골드 3 : 1937 - 욕심쟁이 판다 (0) | 2024.05.09 |
| [JavaScript/DP] 백준 골드 4 : 1915 - 가장 큰 정사각형 (0) | 2024.04.30 |