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

문제 :

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

11052번: 카드 구매하기

분석 :

Bottom-up 방식으로 접근했다. 

d[n] - i개의 카드를 구매시 지불해야 하는 금액의 최대값

n = 1이라면 arr[1]값을 리턴한다.

그리고 for문을 도는데 

n = 2라면 max(d[1] + arr[1], arr[2]) 1개짜리 카드팩 샀을때의 최대값에 1개짜리 카드팩을 더 사는 경우, 2개짜리 카드팩을 사는 경우 중 최대 값을 저장한다.

n = 3 -> max(d[1] + arr[2], d[2] + arr[1], arr[3])  1개짜리 카드팩 샀을때의 최대값에 2개짜리 카드팩 사는 경우, 2개짜리 카드팩 샀을때 최대 값에 한개짜리 카드팩을 사는 경우, 3개짜리 카드팩을 사는 경우

... 를 반복적으로 수행하면 점화식은 아래 코드와 같다 !!

 

Swift 코드 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/04/19.
//

import Foundation
var n = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map { Int(String($0))! }
var d = Array(repeating: 0, count: n + 1)
arr.insert(0, at: 0)
d[1] = arr[1]

for i in 2..<n+1 {
    var maxValue = 0
    for j in 1..<i {
        maxValue = max(maxValue, d[j] + arr[i-j])
    }
    d[i] = max(arr[i], maxValue)
}

print(d[n])