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

문제 설명

백준 11053번 문제 링크

입력 및 출력

» 입력

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

» 출력

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

예제 입출력(테스트케이스)

입력	출력
6 10 20 10 30 20 50	4

문제 풀이(SWIFT) 1

//
//  main.swift
//  BOJ11053_SWIFT
//
//  Created by choiyoujun on 2022/02/08.
//

let A = Int(readLine()!)!
let list = readLine()!.split(separator: " ").map { Int($0)! }
var arr = [Int](repeating: 0, count: A)
var dp = [Int](repeating: 1, count: A)

for i in 0..<A {
    arr[i] = list[i]
}

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

print(count)