[Swift][DP] 백준 11053번 (가장 긴 증가하는 부분수열)

요구능력 : DP의 응용

 

코드설명 : 

 

이 문제는 앞에있는 숫자가 자기자신보다 작은 숫자의 갯수를 세는것이다.

 

1. 배열에서 현재 i가 위치한 배열의 앞부분에 현재 arr[i]의 수보다 작은게 있으면 그 자리의 dp는

dp[i]와 dp[j] + 1 중 큰 수를 dp[i]에 넣는다.

그 이유는 디버깅해보면 알겠지만,

[10, 20, 10, 30]과 같은 경우에

10일 때는 dp[0] = 1

20일 때는 dp[1] = 2

10일 때는 dp[2] = 1

30일 때는 dp[3] = 3 이 된다.

 

후기 : 증가하는 부분수열의 점화식은 처음에 구했는데 왜 답이 안나왔었는지 멀리돌아서 왔다.

let a = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int($0)!}
var dp = Array(repeating: 1, count: 1001)

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