BOJ-11722 가장 긴 감소하는 부분 수열 Swift

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

내가 푼 풀이

- 이제까지 가장 긴 증가하는 부분수열에 대해 많이 풀어봤다.

- 같은 알고리즘에 등호만 다르다.

- dp[n] = a를 n번째원소까지의 감소하는 부분수열의 길이라 정의하자.

- 각 원소는 원소하나만으로 감소하는 부분수열의 길이 1을 갖는다.

- n번째 원소는 n-1번째 원소까지 값을 비교하며, n번째원소보다 작고, 중복되지 않는다면, dp[n]의 값을 증가시킨다.

 

예시로 주어진 [10,30,10,20,20,10] 수열에서

마지막원소 10을 검사할때, 이전의 원소들과 비교를 하게 된다.

20이 두 번 나와도, 첫 번째로 검사한 20에서 dp[n] 값을 증가시켰기 때문에

두 번째 20을 마주쳐도 dp[i] < dp[j] + 1 조건을 만족할 수 없기 때문에 중복되는 원소들을 배제시킬 수 있었다.

 

import Foundation

// 배열 입력받기
let count = Int(readLine()!)!
var arr = [0] + readLine()!.split(separator: " ").map{ Int($0)! }
var dp = Array(repeating: 1, count: count+1)
dp[0] = 0

// dp 입력
// i번째 원소보다 작은 j번째가 있는경우
// 해당하는 값이 이전에 나와있는지를 판단하기위해 dp[i] < dp[j] + 1 조건문을 걸었다.
for i in 1...count {
    for j in 1..<i {
        if arr[i] < arr[j] && dp[i] < dp[j] + 1 {
            dp[i] += 1
        }
    }
}
print(dp.max()!)