[Algorithm/BOJ] 11053 - 가장 긴 증가하는 부분 수열 (DP) Swift

문제 풀이: 

LIS에 대한 개념을 아는 상태라면 쉽게 풀 수 있는 문제이다. 

 

가장 긴 증가하는 부분 수열 (LIS) 

• 하나의 수열이 주어졌을 때, 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 것이다.

아래의 그림을 그리면서 DP를 어떻게 사용해야 하는지 알 수 있었다. 

값이 1인 n개의 요소들을 포함하는 배열을 이용해서 전의 값들을 비교하고 증가되었을 경우에 원래 값에 1을 더해주면서 부분 수열의 최장 길이를 갱신하는 것이다. 

 

코드: 

import Foundation

func solution() -> Int {
    let n = Int(readLine()!)!
    let nums = readLine()!.split(separator: " ").map { Int(String($0))! }
    var dp = [Int](repeating: 1, count: n)
    
    for i in 1..<n {
        for j in 0..<i {
            // i에 해당하는 숫자와 그 전 값들인 j에 해당하는 값을 비교해서 더 작은 값일 때
            if nums[i] > nums[j] {
                // i에 해당하는 최장 길이와 j에 해당하는 최장 길이+1 비교시 더 큰 값
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    // 제일 큰 값이 부분 수열의 최대 길이
    return dp.max()!
}

print(solution())

문제: 

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