[BOJ] 3353 - Printed Circuit Board

https://www.acmicpc.net/problem/3353

BOJ - Printed Circuit Board

문제 유형: 가장 긴 증가하는 부분 수열(LIS)

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 128MB

 

문제

In a printed circuit board, conductive wires are laid on a non-conductive board. Because the conductors in the same layer cannot cross without creating short-circuits, boards with conductors divided into several layers separated by non-conductive board material are used in more complex cases. However, boards with more layers are more expensive. So, manufacturers try to allocate the required conductors to layers in a way that minimizes the number of layers needed.

In this task we look at boards where each conductor is connecting two ports located on opposite edges of the board and seek to minimize the cost of such a board.

Consider, for example, the board shown on the left on the figure below. If one conductor has to connect A to B and another D to C, this could be achieved in a single layer, as shown in the middle on the figure. But a conductor connecting A to C and another connecting D to B could not be laid out in the same layer, as can be seen on the right on the figure.

Write a program that is given the locations of the endpoints of the N conductors on a W × H board and determines the minimal number of layers needed to accommodate all of them.

It may be assumed the width of the conductors is very small compared to the distances between the ports. That is, between any two conductors, there is always enough room for a third one.

 

PCB판에는, 도선이 부도체인 판 위에 있다.

같은 계층의 도선들 간에 교차 시에 합선이 발생할 수 있으므로, 복잡한 회로에서는 여러 층을 써서 배치해야 한다.

그러나, 여러 계층을 만들 수록 더 비용이 많이 들어간다.

그래서, 제작자들은 적절하게 계층에 분배하여 최소화해야 한다.

(그림의 예시 참고)

 

각 도선이 기판의 반대쪽 가장자리에 위치한 두 포트를 연결하는 경우를 고려한다.

도선을 잘 배분하였을 때의 최소 계층을 출력하는 컴퓨터 프로그램을 만드시오.

도선의 폭은 고려하지 않는다.

 

입력

The first line of the text file pcb.in contains N (1 ≤ N ≤ 10^5), the number of connectors. Each of the following N lines contains two integers, Xi1 and Xi2 (0 ≤ Xij ≤ 10^6), separated by a space, meaning that the i-th conductor has to connect the points (Xi1, 0) and (Xi2, H). It may be assumed that all the 2 · N endpoints given in the input are distinct.

 

첫째 줄에 도선의 개수 N이 주어지고, 다음 N개의 줄에 시작점과 끝점이 주어진다. 도선의 정보는 중복되지 않는다.

 

출력

The first and only line of the text file pcb.out should contain a single integer, the minimal number of layers needed to accommodate all the required conductors.

 

적절히 배치했을 때의 최소 계층의 수를 구하시오.

 

풀이

<시작점, 끝점>으로 배열을 생성한다.

시작점 기준으로 도선을 정렬한 뒤, 작은 시작점부터 도선 배치를 시도한다.

배열 brr에 각 계층별 가장 큰 끝자리를 저장한다.

upper_bound를 이용해서 이번 도선이 들어갈 수 있는 가장 큰 위치를 찾는다.

(내림차순 배열에서의 upper_bound == 오름차순에서의 lower_bound)

만약 기존 배열범위를 넘는다면, 새로 도선의 끝점을 추가한다. 즉, 새로운 계층을 만든다는 의미이다.

최종적인 brr배열의 크기를 출력한다.

 

즉, LIS문제를 역으로(Longest Decreasing Subsequence) 푼다고 보면 된다.

 

코드

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func upperBound(target int32, arr []int32) int {
	if len(arr) <= 0 {
		return 0
	}

	l := 0
	r := len(arr)

	for l < r {
		mid := (l + r) >> 1
		if arr[mid] >= target {
			l = mid + 1
		} else {
			r = mid
		}
	}

	return l
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int32
	fmt.Fscan(reader, &n)

	arr := make([][]int32, n)
	for i := int32(0); i < n; i++ {
		var x1, x2 int32
		fmt.Fscan(reader, &x1, &x2)
		arr[i] = []int32{x1, x2}
	}

	sort.Slice(arr, func(i, j int) bool {
		return arr[i][0] < arr[j][0]
	})

	brr := make([]int32, 0)
	for i := int32(0); i < n; i++ {
		pos := upperBound(arr[i][1], brr)

		if pos == len(brr) {
			brr = append(brr, arr[i][1])
		} else {
			brr[pos] = arr[i][1]
		}
	}

	fmt.Fprintln(writer, len(brr))
}