다이나믹 프로그래밍 - 효율적인 화폐 구성(Swift)

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

문제

저작권 문제가 될 수 있어 문제는 삭제합니다.

 

풀이 코드

let n = 3 // 화폐 개수
let m = 7 // 만들어야 하는 금액

let k = [2,3,5]

// 계산하지 못하는 경우를 10001로 초기화해줌
var dp = Array(repeating: 10001, count: m+1)
// 0원인경우는 화폐를 사용하지 않았을때 만들수 있으므로 0으로 초기화
dp[0] = 0

// 화폐단위 개수만큼 반복
for i in 0..<k.count {
    // 화폐단위부터 dp배열 끝까지 반복
    for j in k[i]..<dp.count {
        
        // 맨처음 실행했을때를 보면
        // j = 2
        // k = 2
        // dp[0] 위치의 값이 10001이 아니기때문에
        // 현재 위치의 값과, dp[0] 위치의 값중에 작은값을 현재 위치에 넣어준다.
        // dp[j - k[i]]의 값이 더 작다면 + 1을 해준다.
        if dp[j - k[i]] != 10001 {
            dp[j] = min(dp[j], dp[j - k[i]] + 1)
        }
    }
}

if dp[m] == 10001 {
    print(-1)
} else {
    print(dp[m]) // 2
}


/*
 만들어야 하는 금액 = m
 m = 7
 
 각각의 화폐 = k
 k = 2, k = 3, k = 5
 
 0원부터 만들어야 하는 금액(m)까지 = i
 i = 0
 i = 1
 i = 2
 i = 3
 i = 4
 i = 5
 i = 6
 i = 7
 
 위 데이터로 점화식을 만들면
 점화식 = a(i - k)
 i = 0부터 m까지 각각의 요소
 k = 각각의 화폐 요소
 
 dp[dp[j] - k[i]]
 
 최소한의 화폐 개수를 구해야 하므로 i의 화폐 개수와 i-k + 1의 화폐 개수를 비교해 작은 화폐개수를 고른다.
 */

 

문제 풀이

주석 참고