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

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

 

✅ dp라는데 진짜 어려웠다.

우선 알고리즘 풀이법이 이해가 가지 않았다.

 

주어진 값이 10 20 10 30 20 50 있다고 가정하자.

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

코드를 보면 이해할 수 있는데, 어떤 수를 기준으로 나보다 작은 수를 비교한다.

나를 기준으로 내 앞을 비교한다. 나보다 작은 수(j)라고 하면 dp[j]는 dp[j]보다 작은 값들이 몇개 있는지 저장한다. 그게 가장 긴 부분 수열의 합이기 때문이다.

 

제일 중요한 것은 실제 문제 풀이에서 이를 떠올려야 한다는 점이다. 그렇다면 점화식을 어떻게 생각할 수 있을까?dp문제의 경우에는 그냥 손으로 쓰다보면 특정한 패턴을 찾을 수 있다.list를 놓고, 나보다 작은 수를 서칭하자라는 패턴을 찾았다면 아래에 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()!)