BOJ 2352 반도체 설계

출처: www.acmicpc.net/problem/2352

분류: Greedy, LIS

---

접근방식

포트에 선이 서로 꼬이지 않게 연결하려고 할 때 가장 많이 연결할 수 있는 개수를 찾는 문제입니다.

문제의 예처럼 이렇게 연결되어 있을 때, 왼쪽을 A포트 오른쪽을 B포트라고 생각해보겠습니다.

A[1] -- B[4] 포트가 연결되어 있다면

왼쪽에서 A[1]을 제외한 나머지 포트들은 모두 1보다 크기 때문에 

B에서 4보다 작은 포트들에는 연결할 수가 없습니다.

 

다시말해 A[i] 포트 --> B[j] 포트로 연결하려고 할 때 현재까지 B에 연결되어있는 포트 중 가장 큰 녀석보다 작은 경우에는 연결할 수가 없게 됩니다.

즉, 이 경우엔 B에 연결해야 하는 포트들 중에서 연속적으로 증가하는 수의 최대 길이가 몇이야? 라고 묻는 것과 같습니다.

== LIS(Longest Increase Sequence) 최장 증가 수열을 찾는 문제입니다.

 

해결방법

최장 문제 수열로 풀었습니당

let n = Int(readLine()!)!
let ports = readLine()!.split(separator: " ").map{Int(String($0))!}

// O(logN)
func binSearchLower(array arr: [Int], target: Int) -> Int {
    var low = 0
    var high = arr.count
    var mid = 0
    
    while low < high {
        mid = (low + high)/2
        
        if target <= arr[mid] {
            high = mid
        } else {
            low = mid+1
        }
    }
    return low < arr.count ? low : arr.count-1
}

// Longest Incresing sequence
// O(N)
func findLIS(array ports: [Int]) -> Int {
    var arr = [Int]()
    for port in ports {
        // minIncreses의 마지막 값보다 크면 푸시, 아니면 위치를 찾아서 바꿔준다.
        if arr.isEmpty || port > arr.last! {
            arr.append(port)
        } else {
            let index = binSearchLower(array: arr, target: port)
            arr[index] = port
            //print(port, index, arr)
        }
    }
    
    return arr.count
}

func main() {
    // O(nlogN)
    let lis = findLIS(array: ports)
    print(lis)
}

main()

 

배운점

그리디는 풀다보면 정말 여러 개념이 복합적으로 들어가는 것 같습니다.

이번 문제를 풀기 위해 LIS, 이진탐색, 이진탐색 Lower bound를 공부했네요

문제고 그냥 슥슥 쉽게 풀면 좋겠지만...

아쉽게도 전 그런 천재가 아니니 여러 이론을 많이 정확하게 이해하면서 해나가는 과정이 필요하겠습니다.
(모르면 못풀겠어요 😥😭😇)

갈 길이 멀군요..

화이팅