[백준] (Swift) 11052번 - 카드 구매하기 (dp max 값 구하기)

문제 링크

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

11052번: 카드 구매하기

 

내가 푼 풀이 - 맞았습니다!

• 예제 1번을 활용하여 생각해보자.
• 카드 개수 n, 입력되는 각 카드팩의 가격을 배열 p , 카드 n 개를 구매할 때의 최대 금액을 배열 dp에 넣을 것
• 카드 4개, 가격 p = [1, 5, 6, 7] 일때
• dp = [0, 0, 0, 0, 0] → 인덱스 값을 맞추기 위해서 n+1 개 만큼 dp를 0배열로 정의

이렇게 정의한 뒤, dp 배열에 어떻게 max 값을 넣을지 고민해보아야 한다.

카드 4개를 구매하는데, 최고금액을 구해야하면

1. 카드 3개를 구매하는 최댓값 + 1개짜리 카드팩 구매 
   • 카드 3개를 구매하는 방법은  1, 1, 1  /  2, 1  /  3  이렇게 세가지 겠지? 우리는 어차피 최대 금액만 필요하니까, 이 세가지 중 가장 max 값만 찾으면 되는 거임.
2. 카드 2개를 구매하는 최댓값 + 2개짜리 카드팩 구매
3. 카드 1개를 구매하는 최댓값 + 3개짜리 카드팩 구매
4. 카드 0개를 구매하는 최댓값 + 4개짜리 카드팩 구매

이렇게 네 가지의 금액중 최고 금액을 찾으면 된다.

그럼 여기서, 위 네가지 경우를 가지고 도식화를 해보자. dp에다가 최대값을 넣기로 했으니까, 아래와 같은 도식을 도출해낼 수 있다.

1. dp[4-1] + p[1]
2. dp[4-2] + p[2]
3. dp[4-3] + p[3]
4. dp[4-4] + p[4]

이 네가지중 최댓값을 dp[4] 에 넣으면 정답이다!!

즉, dp[n] 을 구하기 위해서는 이중 for문을 사용하여 dp에 들어갈 값들을 구해주면 된다. 이를 코드로 구현한 소스코드는 아래와 같다.

let n = Int(readLine()!)!
let p = readLine()!.split(separator: " ").map { Int(String($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]+p[j-1])
    }
}
print(dp[n])

 

 

 

dp 는 어려운것같은데 ㅠ 왜 이해가 빠릣빠릣 하게 안될까.. 더 많은 연습이 필요할 것같다. min 한 경우의 수를 찾는 문제를 또 살펴보고, 해당 문제처럼 max 값을 찾는 문제도 익혀두자.