BOJ-2293 동전 1 Swift

문제

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

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

입력

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

출력

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

내가 푼 풀이

- 처음에는 dp[n] = max(dp[n-r] + 1, dp[n]) 의 방법으로 풀었다.

- 위 방법은 동전의 구성이 같고 순서만 달라도 다른경우로 취급했을 경우의 경우의수이다.

- 문제의 핵심은 k가치인 동전으로 k보다 가치가 낮게 만들 수 없다는것이다.

- 가치가 담긴 배열을 오름차순으로 정렬후, 낮은가치부터 dp에 저장한다

- dp[n]: n원을 만들 수 있는 경우의 수

 

 

동전가치의 배열: [1,2] , dp[k]: k원을 만드는 경우의 수

n	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
1, 2	1	2	2	3	3	4	4	5	5

 

1,2 가치의 동전들로 0원을 만드는 경우의 수는 동전을 사용하지않는경우 1가지이다.

dp[0] = 1

n = 1 일때, dp[2] = dp[2] + dp[2 - 1] = 1

n= 2 일때, dp[2] = dp[2] + dp[2 - 2] = dp[2] + dp[0] = 2

 

점화식: dp[n] = dp[n] + dp[n-현재동전의가치] ( n >= 현재 동전의가치)

 

 

import Foundation

let inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [Int]()
var dp = Array(repeating: 0, count: inputs[1]+1)
for i in 0..<inputs[0] {
    arr.append(Int(readLine()!)!)
}
// 동전의 가치 오름차순으로 정렬
// 동전들로 0원을 만드는 경우의 수는 1가지 (동전을 쓰지않는방법)
arr.sort{ $0 < $1 }
dp[0] = 1

// k가치의 동전은 k보다 낮은가치를 만들 수 없다.
// 동전들마다 만들 수 있는 경우의 수를 dp에 저장한다.
// dp[n]: n원으로 만들 수 있는 경우의 수
for i in 0..<arr.count {
    for j in 0..<dp.count {
        if j-arr[i] >= 0 {
            if dp[j] + dp[j-arr[i]] >= Int(pow(2.0, 31.0)) {
                dp[j] = 0
            } else {
                dp[j] = dp[j] + dp[j-arr[i]]
            }
        }
    }
}

print(dp[inputs[1]])