[백준] 11722 가장 긴 감소하는 부분 수열

문제

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

입력

n: Int = 수열의 길이
arr: [Int] = 수열 

1 <= n <= 1000
1 <= arr[i] <= 1000

결과

ans: Int = 가장 긴 감소하는 부분 수열 길이

해석

LIS의 형태로 간단한 점화식을 세울 수 있다.

 

dp[i] = i 전까지 가장 긴 감소하는 부분 수열 길이

 

반복문 한개는 i = 현재 값 , 나머지 반복문 j = i 직전까지

총 최대 1000 x 1000을 돌며  arr[j] > arr[i] 일 때 dp 배열을 갱신한다. 

코드

import Foundation

let n = Int(readLine()!)!

let arr = [-1] + readLine()!.components(separatedBy: " ").map{Int($0)!}
 
var dp: [Int] = [Int](repeating: 0, count: n+1) // dp[i] = arr[i] 전 까지 가장 긴 감소하는 수열

var ans: Int = 0

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

print(ans+1) // 자신을 길이에 추가