[Swift] 백준_전깃줄(2565)(LIS)

문제

 

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

2565번: 전깃줄

 

 

풀이

 

이 문제를 처음 봤을 땐, 어떻게 dp로 풀어야하는지 전혀 감이 안왔다. 그래서 검색을 해보니 LIS와 관련이 있다고했다.

 

LIS란 최장 증가 부분 수열이라는 의미로, 말그대로 배열 안에서 증가하는 부분 수열중 가장 긴 수열을 의미한다. 예를 들어,

[1,4,5,3,8,6,9]라는 arr배열이 있을 때 최장 증가 부분 수열은 [1,4,5,6,9]를 나타낸다.

 

LIS를 구할 때 dp가 사용되는 것이다. 

위에서 인덱스가 0인 값부터 차례대로 확인해보면, 0인 경우엔 1개 밖에 없으므로 result[0] = 1 이다. (result[k]는 위의 배열에서 인덱스가 k일때의 LIS 길이라고 생각하면된다.)

result[5]의 값을 구하기 위해선 0부터 5까지 배열을 돌면서 확인해야한다. 우선 arr[0]은 arr[5]보다 작으므로 일단 result[5]의 값은 2가 된다.

다음으로 arr[1]도 arr[5]보다 작기 때문에 result[5]의 값은 1이 더 커져 3이된다. 이와 같이 계속 확인해주다가 arr[4]의 경우는 arr[5]보다 크다. 이 경우에는 그대로 넘어간다.

 

이렇게 LIS를 구할 수 있는데, 이 문제에서도 LIS를 이용해야한다. 

즉, 주어진 입력의 왼쪽 값을 기준으로 정렬을 해준 뒤에 LIS의 길이를 구한 뒤에 n에서 이 값을 빼주면 답을 구할 수 있다.

import Foundation

let n = Int(readLine()!)!
var lines: [[Int]] = []
for _ in 0..<n {
    lines.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
lines = lines.sorted { $0[0] < $1[0] }
var arr = Array(repeating: 1, count: n + 1)
for i in 0..<n {
    for j in 0...i {
        if lines[i][1] > lines[j][1] {
            arr[i] = max(arr[i], arr[j] + 1)
        }
    }
}
print(n - arr.max()!)

 

 

_____________________________________________________________________________________________________

 

 

한 번도 보지 못한 개념이라 어려웠지만 하나 더 배웠음.