문제 정보


image

풀이

다이나믹 프로그래밍

전체 문제의 최적해가 부분 문제의 최적해로부터 만들어지는 알고리즘이다

  • 하나의 문제를 단 한 번의 연산으로 해결하기 위해, 즉 전체 문제를 풀 때, 동일한 계산을 반복하지 않기 위해
  • Table에 부분문제의 solution을 저장한다
  • 항상 최적의 해를 보장하지만
  • Table에 부분문제의 solution을 저장하므로 많은 메모리를 차지한다

알고리즘 설계

해당 문제의 예시로 dp 배열을 생성해보면 다음과 같다.

dp[0] = 0
dp[1] = 1 (1)
dp[2] = 2 (1+1)
dp[3] = 3 (1+1+1)
dp[4] = 4 (1+1+1+1)
dp[5] = 1 (5)
dp[6] = 2 (5+1)
dp[7] = 3 (5+1+1)
dp[8] = 4 (5+1+1+1)
dp[9] = 5 (5+1+1+1+1)
dp[10] = 2 (5+5)
dp[11] = 3 (5+5+1)
dp[12] = 1 (12)
dp[13] = 2 (12+1)
dp[14] = 3 (12+1+1)
dp[15] = 3 (5+5+5)

dp[i]번째 항목은 동전들의 조합으로 i원를 만들 때의 최소 동전의 개수이다
각각 dp[i] 항목들은 (가지고 있는 동전의 종류만큼 뺀 값 + 1) 중 가장 작은 값으로 채워넣으면 된다
예를 들어 dp[6] = min(dp[6-1] + 1, dp[6-5] + 1)이고,
dp[13] = min(dp[13-1] + 1, dp[13-5] + 1, dp[13-12] + 1)이 된다

전체 코드

import Foundation

let N = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n,k) = (N[0], N[1])
var dp : [Int] = Array(repeating: 10001, count: k+1)
var num : [Int] = []
dp[0] = 0
for i in 0..<n {
    let a = Int(readLine()!)!
    num.append(a)
}
num.sorted(by: <)
for i in 1...k {
    for j in num {
        if i < j {
            continue
        }
        dp[i] = min(dp[i-j]+1, dp[i])
        }
    }

if dp[k] == 10001 {
    print(-1)
}
else {
    print(dp[k])
}