[Algorithm] 가장 긴 감소하는 부분 수열

[hwangJi-dev]

💬 문제

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

💬 Idea

• dp라는 배열을 만든다. 이 때 dp에는 각 값 별 가장 긴 부분수열의 길이가 저장된다.
• A를 돌면서 이전 인덱스들에 본인보다 큰 값이 있는지 검사한다.
• 만약 본인보다 큰 값이 있다면 해당 인덱스의 dp(가장 긴 부분수열의 길이) + 1 과 자기 자신 중 더 큰 값을 dp에 저장하며 갱신한다.
• dp의 가장 큰 값을 출력한다.

💬 풀이

func solution11722() {
    let N = Int(readLine()!)!
    let A = readLine()!.split(separator: " ").map({ Int(String($0))! })
    var dp = Array(repeating: 1, count: N)
    
    for i in 0..<A.count {
        for j in 0..<i {
            if A[j] > A[i] {
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
    }
    
    print(dp.max()!)
}

solution11722()