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

 

 

• BOJ_11052.swift

• 11052 : 카드 구매하기/ 문제 소개
• 풀이 과정
• 코드 구현

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

11052번: 카드 구매하기

 

11052 : 카드 구매하기 / 문제 소개

 

예전에 dp문제를 풀 때

이 글을 보고 뒤로가기를 눌렀던 적이 있다.

---

민규 소비 스타일을 좀 바꿔야하는데

 

 

민규는 카드깡을 한다. 카드팩에 들어있는 카드에 따라 가격이 다르지만 같은 카드 N개를 구매 할 때 민규가 지불해야 하는 금액이 최대여야 한다... (이래야 좋은거 나온다고 생각함 ㅋㅋ) 

 

카드 i개는 Pi카드팩에 들어있다. 이때 Pi 카드팩의 값은 문제에서 주어진다.

그 예로 

주어진 입력에서

 

N = 4일때

카드 1개 인 카드팩 P1 = 1   금액
카드 2개 인 카드팩 P2 = 5  금액
카드 3개인 카드팩 P3 = 6  금액
카드 4개인 카드팩 P4 = 7  금액

이렇게 문제가 주어진다.

 

N은 민규가 구매하려고 하는 카드 개수다. 이는 카드팩의 전체 개수와도 같다.

풀이 과정

 

위의 입력을 풀이로 할 것이다.

 

아 여기서 dp[N]은 N개의 카드를 선택시 최대의 금액을 저장할 것이다~!

• N == 1

구매 할 수 있는 최대 개수 1이다. 이때의 금액을 dp[1]에 저장했다.

dp[1] = 1

• N == 2

이때 선택 할 수 있는 카드는

 

카드팩 P2를 선택하는 경우, 그리고 dp[1]일때 카드 1을 선택 할 수 있는 최대 경우

즉 dp[2] = max( P2카드 금액 , dp[1] + dp[1] )

P2 = 5 , dp[1] + dp[1] = 2이므로

dp[2] = 5

• N == 3

이때 선택 할 수 있는 카드는

카드팩 P3을 선택하는 경우, 그리고 dp[2]를 선택했을 때 나머지 카드 1을 선택 할 수 있는 최대 경우의 수 dp[1]

즉 dp[3] = max( P3카드 금액 , dp[2] + dp[1] ) 중 큰 값이 저장된다.

둘다 6이므로 dp[3] = 6

• N == 4

이때 선택 할 수 있는 카드는

카드팩 P4를 선택하는 경우, dp[3]일때 나머지 카드 1 중 선택할 수 있는 최대 경우, dp[2] 선택했을 때 나머지 카드 2장 중 선택 할 수 있는 최대 경우

 

dp[4] = max(P4카드 금액, dp[3] + dp[1] , dp[2] + dp[2] ) 

중 dp[2] == 5이므로 dp[2] + dp[2] = 10 인 금액이 제일 큰 값이다.

 

호호,, 

코드 구현

 

import Foundation

/**
 * n   = 민규가 살 카드 개수
 * list = 카드팩(index)에 금액 들어있음
 * dp = 특정 카드개수에서 최대 경우의수로 선택된 금액 저장
 */
func BOJ_11052()
{
    let n    = Int(readLine()!)!
    var list = [0]
    var dp   = list
    list.append(contentsOf: readLine()!.split(separator: " ").map{Int(String($0))!})
    
    for i in 1...n
    {
        var j = i
        dp.append(list[i])
        while j >= i / 2
        {
            dp[i] = max(dp[i], dp[j] + dp[i-j])
            j -= 1
        }
    }
    print(dp[n])
}
BOJ_11052()

 

visit my github