[Swift][DP] 백준 11722번 (가장 긴 감소하는 부분 수열)

요구능력 : DP에대한 이해

 

코드설명 : 

 

가장 긴 증가하는 부분수열 문제와 부등호만 틀리다.

가장 긴 감소하는 부분수열을 구하는 문제이다.

 

예제를 보자.

10 30 10 20 20 10

여기서 i인덱스(3)가 20을 가리킨다고 가정하고 설명하면

arr[0]부터 arr[2]까지의 수 중에서 arr[3]보다 큰 수가 있으면 dp[i]를 갱신해준다.

감소하는 부분수열이라서 앞에 나보다 큰 수가 있으면 dp[i]를 갱신해주는것이다.

그럼 dp[i]는 dp[0]부터 dp[2]까지 중에 조건을 만족하는 dp[]를 갖고 +1을 해줄것이다.

dp[1]도만족하고 dp[2]도 만족하는 경우가 있으면 max()로 그 중 큰 값을 가져온다.

이유는 그 중 큰값은 이전에 더 많은 감소하는 부분수열을 갖고있을 것이기 때문이다.

 

간단하게 생각하면 숫자하나 정해놓고 이전에 있는 숫자들과 비교해서 조건에 맞으면 +1해서 길이를 추가하는 것이다.

 

후기 : 관련문제를 한번이라도 풀었다면 꽤나 간단한 문제이다.

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

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