[백준] (Swift) 14002번 - 가장 긴 증가하는 부분 수열4 (dp, LIS value 출력하기)

문제 링크

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

14002번: 가장 긴 증가하는 부분 수열 4

 

문제 풀이 IDEA

우선 해당 문제는 LIS를 구현한 이후에, LIS 부분 수열을 출력하는 문제이기 떄문에 아래 두 개의 포스팅을 모두 이해해야 해당 문제를 수월하게 풀 수 있다.

▷ LIS 란?

https://didu-story.tistory.com/236

[알고리즘] (Swift) 최강 증가 부분 수열 (LIS) 알고리즘 (DP, 동적계획법을 활용한 LIS)

▷ LIS 구현

https://didu-story.tistory.com/237

[백준] (Swift) 11053번 - 가장 긴 증가하는 부분 수열 (DP로 푸는 LIS, 최장 증가 부분 수열 개념)

 

해당 문제는 위 백준 11053문제의 연장으로, LIS 수열을 직접 출력해야한다. 그냥 맨 처음 부터 비교해서 앞수보다 크면 출력하면 돼! 라고 생각하기에는, 문제가 있다. (나의 초반 생각 ㅋㅋ)

[30, 20 , 40, 50 , 60]

위와 같은 수열이 있을 경우, LIS를 구할 때 맨 처음의 30은 제거되는 숫자이다. 30은 제거되고 아래와 같은 부분수열이 최장 증가 부분 수열이 될 것이다. 

[20, 40, 50, 60]

 

따라서 맨 앞에서부터 그냥 이전 수와 비교해서 출력하면 돼~ 라고 생각하기에는 조금 더 복잡하다. 따라서 해결한 방법은 가장 큰 LIS 길이 값을 갖는 부분 부터, 한칸 씩 앞으로 가면서 출력하는 방식이다.

• 가장 큰 dp 값을 갖는 value를 먼저 출력하고, 그다음 큰 dp를 찾아나서는 과정을 코드로 구현
• 단, 가장 큰 값을 갖는 dp의 위치보다 ‘앞'의 value 들만 살펴보면 된다는 것이 핵심! 그래서 maxDP를 구하고, -1 해나가면서 앞에있는 값들이 더 작은지 큰지 판별하는 과정을 진행
• 마지막에 출력할때 reverse 해서 출력해줘야함. (큰 값 부터 뽑았기 때문)

문제에서 주어진 예제를 살펴보자.

예제에서는 [10, 20, 10, 30, 20, 50] 이라는 수열이 주어졌다. LIS를 구하는 과정은 모두 dp 배열에 저장했고, dp 배열 [1, 2, 1, 3, 2, 4]  가 된다. 여기서 가장 큰 LIS 길이를 갖는 것은 dp[5] 이다. 그럼 해당 인덱스 5 를 maxIdx로 저장해두고, 해당 인덱스 보다 "앞"부분으로 전진하면서 차례대로 값을 비교하면 된다. (4, 3, 2, 1, 이렇게 차례대로 비교해야한다. 4보다 작다고 무조건 출력하는게 아니라, 4다음 숫자인 3을 찾고, 3다음숫자인 2를 찾고 이런 방식으로 진행할 것이기 때문에 for 문에서 i 값을 -1 해주면서 값을 찾을 것이다.)

 

소스코드

큰 수 부터 answer에 넣어주었기 때문에, 마지막에 출력할 때도 거꾸로 출력해주어야 한다는 점을 잊지 말자.

let n = Int(readLine()!)!
let inputArray = readLine()!.split(separator: " ").map { Int(String($0))! }
var dp: [Int] = []

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

var maxDp = dp.max()!
var maxIdx = dp.firstIndex(of:maxDp)!
var answer: [Int] = []

while maxIdx >= 0 {
    if dp[maxIdx] == maxDp {
        answer.append(inputArray[maxIdx])
        maxDp -= 1
    }
    maxIdx -= 1
}

for i in stride(from: answer.count-1, through: 0, by: -1) {
    print(answer[i], terminator: " ")
}