[Swift 백준] 11052 카드 구매하기

 

https://www.acmicpc.net/problem/11052

 

풀이 아이디어

- 문제를 요약하면 결국 n개의 카드를 가장 비싸게 사는 법을 구하기

- 즉, 카드 개수를 정확히 N개가 되도록 여러 개의 카드팩을 조합해서 가장 비싸게 구매하는 방법을 찾기

- DP 사용

점화식은 아래와 같다

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

• i장을 구매할 때,
• j장짜리 카드팩을 한 번 사고,
• 나머지 i-j장을 가장 비싸게 살 방법을 dp[i-j]에서 가져오는 것.

풀이

let n = Int(readLine()!)!
let input = readLine()!.split(separator: " ").map {Int($0)!}
var dp = [Int](repeating: 0, count: n+1)

for i in 1..<n+1 {
    for j in 1..<i+1 {
        dp[i] = max(dp[i], dp[i-j]+input[j-1])
    }
}
print(dp[n])