[Swift][DP] 백준 11055번 (가장 큰 증가 부분 수열)

요구능력 : DP에대한 이해

 

코드설명 : 

 

이 문제는 가장 큰 증가 부분수열로 이전에 풀었던 가장 긴 증가 부분수열이랑 비슷하다.

우선 dp를 구하는 방법부터 알아보자

10

1 100 2 50 60 3 5 6 7 8

위와 같이 예제가 있을 때

dp[1] = 1

dp[2] = 101

dp[3] = 3

.

.

.

이렇게 될것이다.

dp[x] = y라고 했을 때

x번 인덱스까지 가장 큰 증가하는 부분수열은 y라는 의미이다.

 

이제 점화식을 구하면 되는데

dp[1]도 함께 처리하기 위해 dp[i]에 arr의 값을 전부 넣어준다.

그리고 arr을 비교하면서 dp[i]의 값을 정해준다.

 

점화식

dp[i] = max(dp[j] + arr[i - 1], dp[i])

 

arr에서 i - 1을 해준건 arr의 인덱스는 0부터 시작하고 dp의 인덱스는 1부터 시작하기 때문이다.

max로 dp[i]값과 계속해서 비교해주는 이유는 dp[i]값이 dp[1]부터 dp[i]까지 + arr[i - 1] 을 하여 값이 계속해서 바뀌는데,

dp[1]부터 dp[i]까지 가는중에 if조건을 만족하지만, 다음번째 dp에 쌓여있는 값이 이전에 쌓여있던 값보다 작을 수 있기 때문이다.

 

 

후기 : 관련문제를 한번이라도 풀었다면 꽤나 간단한 문제이다.

let a = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: 0, count: 1001)
for i in stride(from: 1, through: a, by: 1){
    dp[i] = arr[i - 1]
    for j in 1...i{
        if arr[i - 1] > arr[j - 1] {
            dp[i] = max(dp[j] + arr[i - 1], dp[i])
        }
    }
}
print(dp.max()!)