[Swift] BOJ 11053 가장 긴 증가하는 부분 수열

BOJ 11053 가장 긴 증가하는 부분 수열

 

접근 방식

 

각 원소를 끝으로 하는 가장 긴 증가 부분 수열의 길이를 dp에 저장하는 문제. dp[i]는 list[i]로 끝나는 부분 수열의 최대 길이이고, 자기 앞에서 자기보다 작은 값 j를 찾아 dp[j] + 1 중 최댓값을 취함.

 

주어진 값이 10 20 10 30 20 50 이라고 가정.

 

| list | 10 | 20 | 10 | 30 | 20 | 50 | | --- | --- | --- | --- | --- | --- | --- | | dp | 1 | 2 | 1 | 3 | 2 | 4 |

 

각 i마다 앞쪽 j를 훑어 list[j] < list[i]인 것들의 dp[j] 중 최댓값에 1을 더함. dp는 모두 1로 초기화해 자기 자신만으로도 길이 1이 되게 하고, 마지막에 dp 전체의 최댓값이 답이 됨.

 

코드

 

        let input: Int = Int(readLine()!)!
        let input2 = readLine()
        var list = [Int]()
        
        list = input2!.components(separatedBy: " ").map{ Int($0)! }
        
        var dp = [Int](repeating: 1, count: 1001)
            
        for i in 0..<list.count {
            for j in 0..<i {
                if list[j] < list[i] {
                    dp[i] = max(dp[i], dp[j]+1)
                }
            }
        }
        print(dp.max()!)