백준 꼬인 전깃줄 - boj1365

 

1365번: 꼬인 전깃줄

안녕하세요.

백준의 꼬인 전깃줄 문제입니다.

최장 증가 수열의 길이를 우아하게 돌려돌려 물어보는 문제에요.

이 문제를 풀 때만 해도 LIS의 길이 구하는 방법은 DP, 즉 O(N^2)인 방법만 알고 있었어서 10만...이라는 입력값을 보고 뭔가 이상하다고 생각했습니다.

곱셈이 헷갈려서 계산기로 10만*10만을 해 봤습니다.

그리고 못 푸는 문제다 싶어 호다닥 구글링으로 정답 풀이를 참고해서 풀었습니다.

근데 알고리즘을 알고 나니 제법 쉬운 문제였어요.

구글링하시는 분들도 10만을 보고 놀라서 도망치신 게 분명해요. 그렇죠?

 

문제 설명

문제

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다.

출력

전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.

 

문제풀이 방법

꼬인 전깃줄을 풀기 위해서는 반대편 전봇대와 차례대로 전선을 연결해야 하는데요.

중간에 순서가 꼬이면 안 된다는 뜻입니다. 

1, 2, 3, 4, 7, 6, 5...

이렇게 전선이 연결되어 있다면 7번과 6번 전봇대와 연결되어 있는 전선을 잘라줘야 합니다.

여기서 눈치를 채셨겠지만 7번과 6번을 자르면 1, 2, 3, 4, 5가 남죠.

즉 증가 수열을 구해야 한다는 것입니다.

최소로 전선을 잘라줘야 하니 가장 긴 증가 수열의 길이를 구해주고, 전체 전봇대 수에서 수열의 길이를 빼면 잘라야 하는 전선의 갯수가 나오게 되겠죠.

그렇다고 이 차례대로가 내림차순이어도 되느냐?

그건 아닙니다.

4, 3, 2, 1과 같은 경우에는 4, 3, 2 전부를 잘라줘야 합니다.

남는 전선은 단 1개밖에 없습니다.

2개 이상의 전선이 남는 순간 반드시 꼬이게 되기 때문이에요.

 

간단히 말하자면 LIS의 길이를 구해야 하는데, 입력값이 10만이므로 O(NlogN)의 시간복잡도를 달성하기 위해 이분탐색을 사용해서 효율성을 개선해야 합니다.

LIS를 야무지게 공부한 적이 없어서 이참에 총정리를 했는데 하다 보니 배보다 배꼽이 커져서 따로 정리글을 작성해야겠더라고요.

아래에 링크 첨부해 놓겠습니다.

 

 

정답 코드는 아래와 같습니다.

정답

package gold2

fun main() = with(System.`in`.bufferedReader()) {

	var N = readLine().toInt()
	var arr = readLine().split(" ").map { it.toInt() }.toIntArray()

	var lis = IntArray(N + 1)

	fun lowerBound(num: Int, left: Int, right: Int): Int {
		var l = left
		var r = right

		while (l < r) {
			var mid = (l + r) / 2
			if (lis[mid] < num) l = mid + 1
			else r = mid
		}
		return r
	}

	var idx = 0

	for (i in 0 until N) {
		if (idx == 0) lis[idx++] = arr[i]
		else {
			if (lis[idx - 1] < arr[i]) lis[idx++] = arr[i]
			else {
				lis[lowerBound(arr[i], 0, idx)] = arr[i]
			}
		}
	}

	println(N - idx)
}