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

문제 링크

dp 배열에 해당 숫자보다 크기가 작은 숫자의 개수를 넣어 풀어주었다.

수열 [10,20,10,30,20,50] 이 있고
dp는 초기값이 1로 설정되어있는 배열이라고 생각해보자.

먼저 10의 dp 원소값 dp[0] = 1 이다.
본인보다 크기가 작은 수가 없으므로

20의 값 dp[1] = 2이다.
본인보다 크기 작은 수가 하나 있으므로 그 값의 원소값 dp[1]에 1을 더한 것이다

10의 값 dp[2] = 1이다.
본인보다 크기가 작은 수가 없기 때문이다.

30의 값 dp[3] = 3이다.
본인보다 크기 작은 수가 10, 20, 10 이 있으므로
dp[0] +1, dp[1] + 1, dp[2] +1 중 가장 큰 값인 3이다.

20의 값 dp[4] = 2이다
본인보다 작은 수 10, 10이 있으므로
dp[0] + 1, dp[2] + 1 중 가장 큰 값인 2가 dp[4]의 값이된다.

50의 값 dp[5] = 4이다.
본인보다 작은 수 10, 20, 10, 30, 20 이 있고
그 값 중 가장 큰 값인 dp[3] + 1 = 4 가 dp[5]의 값이 된다.

코드로 작성

import Foundation

let num = Int(readLine()!)!
let numArray = readLine()!.split(separator: " ").map { Int(String($0))! }

var dp = Array(repeating: 1, count: num + 1)

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

print(dp.max()!)