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

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

 

코드설명 : 

 

dp라는것은 만들어진 최대값이 중복하여 쓰인다는것을 보고 알았다.

 

1. dp에 P1, P2, ... 이 있을 때 P1+P1이 아닌 P2 자신이 최대값이 될 수 있으므로 편하게 비교하기위해 카드의 가격을 넣어준다.

 

2. dp 1은 비교할게 없으니 2부터 시작해서 최대값이 될 수 있는 숫자를 다 비교해준다.

ex) 6개산다고 가정하면

f(6) = f(5) + f(1)

f(6) = f(4) + (2)

f(6) = f(3) + (3)

과 f(6) 자신이 위의 더한값들보다 클 수 있다.

그래서 아래코드는 하나하나 비교해준 코드이다.

 

 

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

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

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

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

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