[Swift][DP] 백준 16194번 (카드 구매하기 2)

요구능력 : DP의 개념을 아느냐

 

코드설명 : 

 

카드구매하기 

위에 링크를 클릭하고 가면 자세한 설명이되어있다.

위의 링크의 코드와 다른점은 기존의 dp[i] 와 dp[i -j] + dp[j] 를 비교하여 더작은값을 dp[i]에 넣는다는 것이다.

dp[i] = dp[i-j] + dp[j] > dp[i] ? dp[i] : dp[i-j] + dp[j]

 

후기 :  DP개념을 알고, 최소값이 나오는 경우의수를 알고있으면 풀만한문제

 

let n = Int(readLine()!)! //구매하려고하는 카드의개수
let arr = readLine()!.split(separator: " ").map{Int($0)!}
var dp = Array(repeating: 0, count: 10001)

for i in 0..<n {
    dp[i + 1] = arr[i]
}

for i in stride(from: 2, through: n, by: 1) {
    for j in stride(from: 1, to: i, by: 1) {
        dp[i] = dp[i-j] + dp[j] > dp[i] ? dp[i] : dp[i-j] + dp[j]
    }
}

print("\(dp[n])")