[백준] 2293 동전 1

문제

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

 

입력

n = 동전의 종류 (1~100)
k = 목표 금액 (1~10,000)

coins = 각 동전 금액

결과

ans: Int = k 목표 금액을 만들 수 있는 경우의 수

해석

dp를 통한 경우의 수를 카운팅하는 문제 느낌이다.

 

dp 배열의 규칙은 다음과 같다.

 

dp[i] = i원을 만들 수 있는 경우의 수 

 

 dp 배열을 저렇게 잡으면 점화식은 이렇게 따오를 것 같다

 

C를 만들기 위해 B는 동전 A가 부족한 상황이면

dp[c] = dp[b] + dp[a] 상황이다.

코드

import Foundation

let nk = readLine()!.components(separatedBy: " ").map{Int($0)!}

let (n,k) = (nk[0], nk[1])

var coins: [Int] = []

var dp: [Double] = [Double](repeating: 0, count: k+1)



for _ in 0..<n {
    let coin = Int(readLine()!)!
    coins.append(coin)
}

dp[0] = 1 // 0원을 만드는 경우의 수는 1

for coin in coins { // 모든 동전을 순회
    
    if coin > k { continue } // 현재 동전이 목표 값 k보다 크다면 의미 없음
    
    for i in 0...k-coin {
        dp[i+coin] += dp[i] //  i+coin을 만들기위해서는 dp[i]와 coin이 필요하므로, dp[i]의 경우의 수를 누적한다.
    }
}

print(Int64(dp[k]))