[백준/Swift] 11053번: 가장 긴 증가하는 부분 수열

 

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

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

 

dp[i]에 i번째의 앞에서부터 원소까지의 증가 부분 수열의 원소 횟수(길이)가 담긴다

모두 최소 길이가 1이므로 dp에 넣어주면서 진행하고,

앞에 원소들을 확인하면서 진행. 앞에 원소가 나보다 작으면 증가 부분 수열에 들어가므로 그 원소의 dp 값 + 1

그런데, 여기서 시작점이 매번 다르므로 max로 dp[i]와 최댓값을 비교해서 갱신하도록 한다.

 

import Foundation

/*
 가장 긴 증가하는 부분 수열
 */

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

for i in 1...n { //현재 원소
    dp[i] = 1
    for j in 1..<i { //앞에 있는 원소들
        if arr[j-1] < arr[i-1] {
            dp[i] = max(dp[j] + 1, dp[i])
        }
    }
}
print(dp.max()!)