[백준/Swift] 2294 : 동전 2

 

 

• BOJ_2294.swift

• 2294 : 동전 2/ 문제 소개                
• 풀이 과정
• 코드 구현

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

2294번: 동전 2

2294 :  동전 2 / 문제 소개

 

n가지 종류의 동전이 있다.

적당~히 사용해서 k원이 되도록 하고 싶다. 적당히가 아니라 동전의 개수가 최소로 k원을 만들려고한다.

각각의 동전은 계속해서 사용할 수 있고, k원을 만들지 못한다면 -1을 출력 해야 한다.

풀이 과정

 

이 문제는 동전 1과 다른 문제입니다. 

주어진 동전들을 바탕으로

특정 동전일 때부터 0 부터 k원까지!! 근데 이전에 구한 최소의 경우의 수가 있다면 그것을 이용하면서 풀면됩니다.

 

규칙을 찾아야 합니다.

 

동전들은 list배열에 집어넣고,

for i in 0..<n
{
	if list[i] <=k
    {
    	for j in list[i]...k
        {
        	dp[j] = ...

이중 포문을 통해서 동전 개수부터(왜냐면 그 동전 크기 이전의 x원은 만들수가 없다고 판단했습니다.

동전 j == list[i]일때부터 탐색을 해나갔습니다.

근데 list[i]는 특정한 동전인데 이것을 어떻게 추가시켜 나가야 하는지 고민이 었는데.. 알고보니 동전 한개 사용한다는건 +1을 해주면 된다는 것이었습니다...

그럼 나머지 동전은,  (0..j...k)구하려는 특정 가격 j원 - (동전한개쓴거)list[i]를 한 값을 dp[]에서 찾으면 됩니다.

코드 구현

 

import Foundation

func BOJ_2294()
{
    let nk   = readLine()!.split(separator:" ").map{Int(String($0))!}
    let n    = nk[0]
    let k    = nk[1]
    var dp   = Array(repeating: 10001, count: k+1)
    var list = [Int]()
    for _ in 0..<n
    {
        list.append(Int(readLine()!)!)
    }
    dp[0] = 0
    for i in 0..<n
    {
        if list[i] <= k
        {
            for j in list[i]...k
            {
                dp[j] = min(dp[j-list[i]] + 1 , dp[j])
            }
        }
    }
    print(dp[k] == 10001 ? -1 : dp[k])
}
BOJ_2294()

 

visit my github