[백준/Swift] 2565 : 전깃줄

 

 

• BOJ_2565.swift

• 2565 : 전깃줄/ 문제 소개
• 풀이 과정
• 코드 구현

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

2565번: 전깃줄

2565 :  전깃줄 / 문제 소개

 

전봇대 A와 B가 있다.

전봇대에 전깃줄을 추가하는데 교차하면 안된다.(합선의 위험)

합선의 위험이 있어 전깃줄에서 몇개의 전깃줄을 없애 교차하지 않도록 만들려고 한다.

이때 교차하지 않게 만들기 위해 없애야 하는 전깃줄 최소 개수를 구해라!

풀이 과정

 

입력을 보면 전깃줄 개수는 100 이하의 자연수이고, A전봇대와 B전봇대의 위치가 있는데 500 이하의 자연수이다.

 

이 문제 무척 고민을 했는데... 반례도 생각하고 해결하면서 풀었는데 계속 틀려 찾아보니 풀지 못한 반례가 있었다.

toonraon님이 쓰신,, 

그림 1

이 반례다.

---

이 문제는 LIS(Longest Increasing Subsequence)의 관점으로 놓고 풀면 쉽게 풀어진다...

LIS란 최장 증가 부분 수열이다.

 

최장 증가 부분수열의 관점에서 전깃줄 문제를 풀게 된다면

일단 입력값의 전깃줄 위치는 무작위인데 왼쪽 전봇대, 또는 오른쪽 전봇대 둘중 하나를 정해서 sort 한 이후에

그 반대 전깃줄의 번호들 중에, 증가하는 부분 수열의 개수를 찾아가면 된다.

 

예를들어 

input

5

1 3

6 4

4 6

3 1

2 5

이런 인풋이 있으면.

(왼쪽 전봇대 번호, 오른쪽 전봇대 번호) 한 쌍을 저장하는 배열을 생성하면된다. 

배열에서 왼쪽 전봇대 번호를 정렬하면

왼쪽 전봇대     :    1    2    3    4    6

오른쪽 전봇대 :    3    5    1     6    4

이제 오른쪽 전봇대에서 나올 수 있는, 증가하는 수열의 최대 값은

3 5 6이 된다. 이 경우는 LIS이다. 결국 한쪽 전봇대를 소팅하면 다른 한쪽 전봇대에서 꼬이지 않게 최대한 선을 연결하는 과정은 LIS 문제가 되는 것이다.

 

증가하는 수열의 최대값을 구하면 전체 전깃줄 개수에서 증가한는 수열 최대 개수를 뺀 값이 정답이다.

코드 구현

 

import Foundation
typealias Element = (left: Int,right: Int)

func BOJ_2565()
{
    let n        = Int(readLine()!)!
    var line     = [Element]()
    var length   = Array(repeating:1, count: n)
    
    for _ in 0..<n
    {
        let input = readLine()!.split(separator:" ").map{Int(String($0))!}
        line.append((input[0],input[1]))
    }
    line.sort
    {
        if $0.left < $1.left
        {
            return true
        }
        return false
    }
    for i in 0..<n
    {
        for j in 0..<i
        {
            if line[j].right < line[i].right
            {
                length[i] = max(length[i],length[j] + 1)
            }
        }
    }
    print(n - length.sorted()[n-1])
}
BOJ_2565()

 

visit my github