백준 2293 동전 1 - Swift

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

2293번: 동전 1

 

동전 1

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2의 31승보다 작다.

예제 입력 1 

3 10
1
2
5

예제 출력 1 

10

 

풀이방법

 10원 = (1,2)원짜리 동전으로 10원을 만들 수 있는 경우의 수 +(1,2,5)원으로 10원을 만들 수 있는 경우의 수 입니다.

뭔가 전에 계산 했던 것을 이용해서 다음 값을 계산하고 그런 식 인 것 같죠? 그럴 땐 DP입니다.

DP 점화식.. 참 떠올리기 어렵죠. 그럼 일단 2차원 표로 그려봅니다.

저는 2가지 경우로 점화식을 나눴습니다.

1. K가 Coin보다 작을 경우

k = 3, coin = 5 이면 5원짜리 동전으로는 3원을 못만드므로 (1,2)원으로 만들 수 있는 경우의 수

즉, 전에 계산했던 것을 그대로 가져오면 됩니다. 

점화식은 DP[i][j] = DP[i-1][j] // i = row, j = column

2. K가 Coin 보다 크거나 같은 경우

k = 6, Coin = 5 이면 (1,2)원으로 만들 수 있는 경우의 수 + (1,2,5)원으로 만들 수 있는 경우의 수

즉, 전에 계산했던 것 + 알파 입니다.

알파는 점화식을 어떻게 해야 될지 몰라서 다시 표를 봤습니다. 규칙이 있을 것 같아서..

전에 계산했던 것에 무엇을 + 해주어야 올바르게 나오는 지 봤더니

DP[i][k - coin]를  더해주면 답이 나오더군요.

점화식은 DP[i][j] = DP[i-1][j] + DP[i][j-coin] (j >= coin)

 

코드

import Foundation

let NK = readLine()!.split(separator: " ").map{ Int(String($0))! }
let N = NK[0]
let K = NK[1]
var coins = [Int]()
var dp2 = Array(repeating: Array(repeating: 0, count: K+1), count: N)

for _ in 0..<N {
    coins.append(Int(readLine()!)!)
}

// 표 첫줄 계산
for row in 0..<N {
    for col in 1...K {
        if row == 0 && coins[row] <= col {
            if col % coins[row] == 0 {
            dp2[row][col] = 1
            }
        }
    }
}
dp2[0][0] = 1

for i in 0..<N {
    for j in 0...K {
        if i == 0 { continue }
        
        if j < coins[i] {
            dp2[i][j] = dp2[i-1][j]
        } else {
            guard j >= coins[i] else { continue }
            dp2[i][j] = dp2[i-1][j] + dp2[i][j-coins[i]]
        }
        // 경우의 수는 2의 31승보다 작다 (예외 처리)
        if dp2[i][j] >= Int(pow(2.0, 31.0)) { dp2[i][j] = 0 }
    }
}

print(dp2[N-1].last!)