[Swift][DP] 백준 2294 (동전 2)

요구능력 : DP

 

코드설명 : 

 

dp의 초기값을 10001로 설정해준 이유는 이 문제가 최솟값을 찾는 문제이기 때문에 최대값으로 설정해준것이다.

10001이 최댓값인 이유는 k의 범위가 10000까지 이기때문에 여기서 나올 수 있는 가장 큰 수는 1로 10000까지 만들어서 1이 10000개인 경우이다.

 

위의 사진은 직접 행과 열로 나열해서 사용해야하는 동전의 개수를 적은것이다.

 

1원으로 1~15까지 만들 수 있는 경우의 수는 1개 ~ 15개이다.

하지만, 5원으로 1 ~ 15까지 만드려면? 뭔가 복잡해지는것 같을 수 있다.

우선, 1원으로 1 ~ 15까지 만들어보자.

행과 열을 만들어야겠다.

for i in 0..<n{
	coin.append(Int(String(readLine()!))!)
	for j in coin[i]...k{
    	dp[j] = dp[j - 1] + 1
    }
}

이런식으로 만들면 1원으로 15원까지는 성공이다!

 

하지만, 우리는 5원으로 15원, 12원으로 15원도 만들어야한다.

위의 사진을 보면 5원으로 5원만드는 경우의 수는 1개이다.

이 문제에서 필요로 하는건 사용한 동전의 최소 개수이다.

 

현재 1원으로 5원만드는 부분까지 구해져있다.

1원으로 5원 만드려면 1원이 5개가 필요하다.

그럼 dp[5] = 5이다.

하지만, 코인이 5원일 때 5원은 1개로도 만드니까

dp[5] = 1이 되어야한다.

 

이 식을 생각하는건 어떻게 보면 간단한데 처음접하는 사람들은 당연히 어려울 수 있다.

그러니 DP문제는 이런식으로 푸는구나 하고 감을 익히는게 중요한것 같다고 생각한다.

 

dp[5]가 1이 되려면 어떻게 해야할까?

간단히 생각해보면 5원짜리 동전으로 5원을 만드려면 0원에 5원을 더하는 것과 같다고 생각하면된다.

dp[5] = dp[0] + 1이 되면 된다.

 

그럼 5원짜리 동전으로 6원을 만드는 경우는?

1원을 만드는 최소의 경우에 1을 더해준게 바로 6원을 만드는 최소의 경우다.

why?

6원을 만드는 최소의 경우는 결국 1원을 만드는 최소의 경우에 +5만 하면 되기 때문이다.

이해가 안가면 아래를 더 살펴보자

.

.

.

그럼 5원짜리 동전으로 10원을 만드는 경우는?

5원이 만들어지는 최소의 경우에 +1을 한게, 결국 10원을 만드는 최소의 경우이다.

5원을 만드는 경우의 수를 보자

1 + 1 + 1 + 1 + 1

5

여기서 최소의 경우는 5하나만 사용했을 때이다.

그럼 10원을 만드는 최소의 경우는 5 하나만 사용했을 때의 경우에 +5만 해주면 된다.

5 + 5

그럼 2가지.

 

이를 식으로 도출해보면 아래와 같이 나온다.

for i in 0..<n{
	coin.append(Int(String(readLine()!))!)
	for j in coin[i]...k{
    	dp[j] = min(dp[j], dp[j - coin[i]] + 1)
    }
}

 

min을 사용해준 이유는 이미 앞전에 최대 경우들을 세워놨기 때문에(루프를 돌다가도 코인이 커질 수록 경우의 수가 줄어들게됨)

최소값을 구해야해서 사용해줬다.

 

후기 : 어렵지는 않은문제이지만, DP관련 문제는 계속해서 풀면서 감을 잃지 않는게 중요한것 같다.

import Foundation
let nk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nk[0]
let k = nk[1]
var dp = Array(repeating: 10001, count: 10001)
var coin = [Int]()
dp[0] = 0
for i in 0..<n{
    coin.append(Int(String(readLine()!))!)
    for j in stride(from: coin[i], through: k, by: 1){
        dp[j] = min(dp[j], dp[j - coin[i]] + 1)
    }
}
if dp[k] == 10001{
    print(-1)
}else{
    print(dp[k])
}