[Swift][DP] 백준 14002 (가장 긴 증가하는 부분 수열4)

요구능력 : DP에 대한 이해

 

코드설명 : 

 

첫번째로 가장 긴 증가하는 부분수열의 크기를 구해야하는데, 먼저 풀고오는 것을 추천한다.

 

이 문제에서 추가된 부분은 수열을 출력해주는것이다.

dp에 우리가 저장한 수열 크기의 순서는 arr에 저장된 수열의 순서와 동일하다.

이게 무슨소린고 하면 아래 그림과 같다.

이거 처음에 나도 뭔소린가 했는데 밑에 var order = dp.max()! 부분부터 손디버깅 해보면서 써봐야 안다. 직접 생각하면서 써봐라.

참고로 아래 코드에서는 인덱스를 의도적으로 맞추지는 않았는데, dp값을 처음에 1로 초기화해놔서 정답이된다.

 

 

(참고 : 어차피 배열의 뒤쪽에 있는 수가 큰 수 이므로 배열의 뒤쪽부터 찾아주는것이다.)

이제 이 인덱스가 같은점을 이용해서 문제를 푸는데,

dp값이 최대값(order)이되는 시점의 인덱스 먼저 결과를 출력할 배열(result)에 추가해준다.

그리고 최대값으로 필요한 부분의 인덱스는 구해서 추가해줬으니,

이제 최대값보다 하나 작은 값을 갖는 인덱스를 찾아서 배열에 추가해준다.

이런식으로 추가해주다보면 dp를 끝까지 돌게되고, 모든 수를 result에 저장하게된다.

 

이를 거꾸로해서 배열에 추가해주고 출력해주면 끝이다.

 

후기 : 진짜 왜인지 모르겠는데, 이 문제 다른사람들 답안봐도 이해가안가서 엄청고전했다..

개인적으로 어려웠고, 이해가 많이 안갔던 문제이다..

이해하고나니 참 어이가없었다..

진짜.. 시간많이투자했다

let n = Int(String(readLine()!))!
var arr: [Int] = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp: [Int] = Array(repeating: 1, count: 1001)
var result: [Int] = []

for i in 1..<n {
    for j in 0..<i{
        if arr[i] > arr[j]{
            dp[i] = max(dp[i], dp[j] + 1)
        }
    }
}

print(dp.max()!)

var order = dp.max()!
for i in stride(from: n - 1, through: 0, by: -1){
    if dp[i] == order{
        result.append(arr[i])
        order -= 1
    }
    
}
result.reverse()
print(result.map{String($0)}.joined(separator: " "))