[백준] (Swift) 16194번 - 카드 구매하기2 (DP 기초 문제, 최소값 구하기)

문제 링크

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

16194번: 카드 구매하기 2

 

풀이 IDEA

이전 문제 "카드 구매하기"를 먼저 풀어보면 바로 알 수 있는 문제이다.  (복습한다는 생각으로 다시 풀이 아이디어를 적어보자)

• 구매를 원하는 카드의 수를 n , 카드 팩 각각의 가격을 배열 p 에 입력을 받을 것이다.
• dp 배열을 생성하여 조건 범위 밖의 수인 99999 를 n+1 크기만큼 넣어준다.
  • 가장 큰 수 999999를 넣는 이유는, 우리는 min 값을 구할 것이다. 범위 밖에 있는 수를 넣음으로써, 항상 작은 값이 선택되게끔 만들 수 있다.
  • dp 배열에는, 인덱스 순서대로 최소 금액이 들어간다. dp[1] : 카드 1개를 구매할때 최소 금액, dp[2] : 카드 2개를 구매할 때의 최소금액... 이런식으로 말이다.
• 우리가 구하고자 하는 것은, N 장의 카드를 구매할때 최소 금액을 사용해야하는, 이 최소금액이다. 최소금액은 어떻게 구할 수 있을까?
  • 예제 1번을 활용해서 점화식을 구해보자. 우리는 카드 4장이 필요하다. 4장을 구매하기 위해서는 아래와 같이 구매할 수 있다.
  • 카드 3장을 어떤 방식으로든 구매 + 카드 1팩짜리 구매
  • 카드 2장을 어떤 방식으로든 구매 + 카드 2팩짜리 구매
  • 카드 1장을 어떤 방식으로든 구매 + 카드 3팩짜리 구매
  • 카드 0장을 어떤 방식으로든 구매 + 카드 4팩짜리 구매   이렇게 구할 수 있다.
• 그럼 이걸 최소금액으로 생각해보자. 어떻게 하면 최소금액이 나올까?
  • 카드 3장을 최소한의 금액으로 구매하고 + 카드 1팩짜리 구매
  • 카드 2장을 최소한의 금액으로 구매하고 + 카드 2팩짜리 구매
  • 카드 1장을 최소한의 금액으로 구매하고 + 카드 3팩짜리 구매 
  • 카드 0장을 최소한의 금액으로 구매하고 + 카드 4팩짜리 구매  
• 위 네 가지 경우 모두 4장의 카드를 구매하는 경우이고, 이중에서 최소!!금액을 찾으면 우리가 원하는 답이 나온다. 
• 숫자가 두개가 변하는 반복문을 구현하기 위해 이중 for-in 구문을 사용해서 그대로 구현하면 된다.

 

소스코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/16194_%EC%B9%B4%EB%93%9C%20%EA%B5%AC%EB%A7%A4%ED%95%98%EA%B8%B02/main.swift

GitHub - deslog/Algorithm

let n = Int(readLine()!)!
let p = readLine()!.split(separator: " ").map { Int(String($0))! }
var dp = [Int](repeating: 999999, count: n+1)
//최소값을 추출해야하니까 dp 를 조건 범위 밖의 수로 채워넣어주었다.
dp[0] = 0
// 0을 넣어준 이유는, 아래 for 문을 돌면서 i=1,j=1 일때 dp[0]+p[0]이 계산될텐데, 이때 허수 999999 가 들어가면 안되기 때문이다.
for i in 1..<n+1 {
    for j in 1..<i+1 {
        dp[i] = min(dp[i], dp[i-j]+p[j-1])
    }
}
print(dp[n])