[코테] 동전

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

9084번: 동전

 

 

이전 블로그에서 작성한 BOJ 12865 평범한 배낭 문제를 다른 사람의 해답을 참여하고 풀고

그 문제와 비슷한 유형인 BOJ 9084 동전 문제를 스스로 풀어보았다.

 

 

제출한 풀이

import Foundation

let t = Int(readLine()!)!
for _ in 0..<t {
    let n = Int(readLine()!)!
    let coins = readLine()!.components(separatedBy: " ").map({ Int($0) ?? 0 })
    let money = Int(readLine()!)!
    
    var dp = Array(repeating: Array(repeating: 0, count: money+1), count: n+1)
    for i in 1...n {
        let coin = coins[i-1]
        for j in 1...money {
            if j >= coin {
                if j % coin == 0 {
                    dp[i][j] += 1
                }
                for k in 0...(j/coin) {
                    dp[i][j] += dp[i-1][j - k*coin]
                }
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    print(dp[n][money])
}

 

 

현재 지불해야 하는 돈을 j(index)로 하고, 동전을 왼쪽 축인 coin이라 하자.

만일 지불해야 하는 돈(j)이 동전(coin)보다 적으면 이전 dp에서 계산한 값으로 대체한다. 

 

만일 지불해야 하는 돈(j)이 현재 동전보다 크거나 같다면 이제 계산을 시작한다.

j를 coin 값으로 나눈 나머지가 0이라면 이전 coins과 상관 없이 현재 coin만으로도 계산이 가능하므로 dp[i][j]에 1를 더해준다.

그 후에 해당 coin과 이전 coins의 조합으로 돈을 지불할 수 있는 방법의 갯수를 계산한다.

 

j를 coin 값으로 나눈 몫만큼 계산을 진행할 수 있고, for문을 돌려 0부터 해당 몫까지 계산을 진행한다.

예를 들어, 현재 j = 7, coin = 3 인 경우를 계산한다면

j를 coin으로 나눈 값이 2이므로 coin 3을 0개, 1개, 2개와 이전 coins 값을 사용하여 7을 만들 수 있는 값을 계산한다.

 

먼저 k (j/coin) 값이 0일때,

dp[i-1][j - 0 * coin] = dp[i-1][7]이고 coin 2로 7을 만들 수 있는 경우의 수는 0개이다.

k (j/coin) 값이 1일때,

dp[i-1][j - 1 * coin] = dp[i-1][7-3]이고 coin 2로 4을 만들 수 있는 경우의 수는 1개이다.

k (j/coin) 값이 2일때,

dp[i-1][j - 2 * coin] = dp[i-1][7-6]이고 coin 2로 1을 만들 수 있는 경우의 수는 0개이다.

 

그러므로 dp[i][j] = dp[i][7] 값은 1이 된다.

 

이와 비슷하게 계산하면 dp배열을 계산할 수 있다.

 

 

막상 풀이를 다 해보니까 정말 평범한 배낭과 비슷한 유형이라는 것을 알 수 있었다.

DP는 언제 익숙해질까 .....