본고는 BOF 2565에 대한 전반적인 설명과 이를 해결한 방법 등을 기술하기 위해 작성되었습니다.
문제
두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.
예를 들어, <아래 사진>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 젓깃줄이 서로 교차하지 않게 된다.
전깃 줄이 전봇대에 연결되는 위치는 전봇대 위에서 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되어 있는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 전봇대 사의의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.
출력
첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.
예제
입력
8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6출력
3풀이
풀이 방식은 간단했다.
없애야 하는 전깃줄의 최소 개수 = 전체 전깃줄의 개수 - 곂치지 않은 전깃줄의 개수 이므로, 겹치지 않는 전깃줄에 대한 최대 증가수열을 구하면된다.
우선, 노드 탐색을 위해 A전봇대를 기준으로 오름차순 정렬을 진행하면 다음과 같은 형태가 된다.
A B
1 7
2 2
3 9
4 1
6 4
7 6
9 7
10 10A전봇대의 6번 전깃줄(이하 A-6)을 예시로 들어보자,
A전봇대와 연결되어 있는 B전봇대의 4번 전깃줄(이하 B-4)은 A(1~n)와 연결돼 있는 B보다 큰 수여야 한다.
그래야 A-6 - B-4 라인과 겹치지 않기 때문이다.
위와 같이 A-8과 연결된 B 라인이, 비교하는 수의 B값 보다 작다면, 겹치는 선이 되어버리기 때문이다.
그럼 우리는 아래와 같이 로직을 만들 수 있다.
N = 전기술의 개수
Lines = {
first: A 전깃줄
second: B 전깃줄
}
for (let i = 1; i <= N; i++) {
for (let j = 1; j <=N; j++) {
if (Lines[i].second)
}
}본 문제는 전기줄의 총 겹치지 않는 갯수를 구해야 하므로 LIS (최대증가수열)을 사용하면 다음과 같은 로직으로 처리할 수 있다.
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n')
const length = +input.shift()
const numbers = input.map(e => e.split(' ').map(Number))
const sortedNumbers = numbers.sort((a, b) => a[0] - b[0])
const dp = Array.from({ length: length }, () => 0)
// 첫째 줄은 항상 연결이 가능하므로 1
for (let i = 0; i < length; i++) { // A 1부터 10까지 순회하는 반복문
dp[i] = 1
for (let j = 0; j < length; j++) { // A 비교 지점부터 10까지 순회하는 반복문
if (sortedNumbers[i][1] > sortedNumbers[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
console.log(length - Math.max(...dp))