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

 

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

11052번: 카드 구매하기

 

일반적인 dp 유형 문제인 것 같은데 굉장히 헷갈렸다.

 

 

이렇게 구상했다.

가장 헷갈렸던 것이 바로 dp의 정의였다. 

여기서 dp는 i장 카드를 살 때의 최대 비용을 저장하는 배열로 사용한다.

dp가 그렇듯 앞에 작은 문제들의 답으로 큰 문제의 답을 해결할 수 있도록 해야 하는데, 여기서는 카드 N장을 구매할 때의 최대 비용을 구해야 하므로, 1장~N-1장을 구매했을 때의 최대 비용부터 차례대로 구하면서 N장의 최대 비용을 구할 수 있다.

 

dp[i]에는 i장을 구매할 때의 최대 비용이 들어있어서 i+1장을 구매할 땐, dp[i] + card[i] 를 해주면 된다!

이것의 점화식은 바로!!

 

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

 

 

[전체 코드]

import Foundation

let n = Int(readLine()!)!
var card = readLine()!.split(separator: " ").map{ Int(String($0))! }
card.insert(0, at: card.startIndex)
var dp = [Int](repeating: 0, count: n+2)

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

 

너무 헷갈렸지만 재미있는 문제였다!! 다음에 내가 잘 풀 수 있을지 모르겠지만... 열심히 연습해야겠따.