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

 

 

 

---

풀이

 

문제를 이해해보자.

• 동전의 개수는 제한이 없고, 개수를 여러번 사용하여 가치를 만들면 된다.
• 동전의 구성이 같다면, 순서가 다르더라도 같다.
• 가치의 합이 k원인 경우의 수를 구하여라.

 

경우의 수를 구하는 문제인데 동전의 개수에 집중하지 말고 해당 동전을 사용하여 k 가치를 만들 수 있느냐에 집중하면

dp를 사용해야 한다는 걸 알 수 있다.

dp로 이전의 경우의 수 + 해당 동전으로 k 가치를 만들 수 있는가에 집중해보자.

 

---

설계

 

 

동전의 개수 제한없이 입력된 n개의 동전의 가치를 사용하여 k 가치를 만들 수 있는지만 확인하면 된다.

 

예제 1을 생각해보자.

 

k가 1~10인 경우에 [1, 2, 5]의 가치를 가진 동전이 해당 k를 만들 수 있는 경우이다.

 

n\k	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	2	3	3	4	4	5	5	6
5	1	2	2	3	4	5	6	7	8	10

 

 

---

구현

 

위의 설계를 바탕으로 dp의 점화식을 구할 수 있다.

 

dp[i] = dp[i] + dp[i-v]

 

 

---

전체코드

 

import Foundation
let input = readLine()!.split(separator: " ").map{Int(String($0))!}

let (n,k) = (input[0], input[1])
var dp = [Int](repeating: 0, count: k+1)

var values: [Int] = []

for _ in 0..<n{
    let value = Int(readLine()!)!
    values.append(value)
}

dp[0] = 1

for v in values{
    if k>=v{
        for i in v...k{
            if dp[i] < Int(pow(2.0, 31.0)){
                dp[i] += dp[i-v]
            }
        }
    }
}

print(dp[k])