swift ) 백준 14002 - 가장 긴 증가하는 부분 수열 4

let n = Int(readLine()!)!

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

var dp = [Int:Int]()
var result = [Int]()

// LIS (최장부분수열 찾기)
for i in 0..<n {
	dp[i] = 1
	for j in (0..<i).reversed() {
		if num[i] > num[j] {
			dp[i] = max(dp[i]!, dp[j]!+1)
		}
	}
}

// 최장부분수열을 역으로 배열에서 찾아서 출력
let lisIndex = dp.keys.filter{dp[$0] == dp.values.max()!}
var index = lisIndex[0]
result.append(num[index])

for i in (0..<lisIndex[0]).reversed() {
	if dp[i] == dp[index]! - 1 && num[i] < result.last! {
		result.append(num[i])
		index = i
	}
}
print(dp[lisIndex[0]]!)
print(result.reversed().map{String($0)}.joined(separator: " "))

 

최장부분수열만 찾는건 크게 어렵지 않았지만

그 값을 출력해야하는 게 까다로웠다..

O(N^2)이기도 하고 코드가 깔끔하지가 않아서..

다른 코드도 조금 둘러보는 게 좋을듯..