[알고리즘/Swift] 2293 동전 1
문제 정보
풀이
다이나믹 프로그래밍
전체 문제의 최적해가 부분 문제의 최적해로부터 만들어지는 알고리즘이다
- 하나의 문제를 단 한 번의 연산으로 해결하기 위해, 즉 전체 문제를 풀 때, 동일한 계산을 반복하지 않기 위해
- Table에 부분문제의 solution을 저장한다
- 항상 최적의 해를 보장하지만
- Table에 부분문제의 solution을 저장하므로 많은 메모리를 차지한다
알고리즘 설계
아래의 그림과 같이 다이나믹 프로그래밍 배열을 하나 생성하여 부분 문제의 해에 해당하는 값들을 넣어주었다
i : 해당 동전까지 사용할 수 있을 때 만들 수 있는 경우의 수
j : 가치의 합을 1원부터 k원까지 만들 수 있는 경우의 수
라고 설정하였다
예를 들어 i = 2, j = 5일 때 해당 배열 numArray[2][5] 에는, 동전을 1원짜리랑, 2원 짜리 두 개를 사용할 수 있을 때, 5원을 만들 수 있는 경우의 수가 들어간다
이렇게 모든 배열을 다 채운 후, 가장 마지막 원소를 출력하면 그 값이 1원, 2원, 5원 총 3개의 동전으로 10원을 만들 수 있는 경우의 수가 나온다
이러한 배열을 채울 때 dp(다이나믹 프로그래밍) 알고리즘을 사용하였다
특정 동전까지 사용할 수 있을 때, 특정 가치의 합을 구하려고 할 때, 특정 동전을 사용할 수 없는 경우와 있는 경우로 나눠서 문제를 풀었다
- 특정 동전을 사용할 수 없는 경우
- 해당 동전의 가치가 구하려는 특정 가치의 합보다 클 경우 특정 동전을 사용할 수 없다
- 이럴 때에는 직전 동전에서 구할 수 있는 경우의 수와 같다
- 예를 들어, 1원, 2원, 5원의 동전을 사용할 수 있을 때, 총 4원의 가치의 합의 경우의 수을 구할 때 5원은 사용할 수 없다
- 이런 경우, 1원, 2원으로 총 4원의 가치의 합을 만드는 경우의 수와 같으므로
numArray[i][j] = numArray[i-1][j]
값을 넣어준다
- 특정 동전을 사용할 수 있는 경우
- 해당 동전의 가치가 구하려는 특정 가치의 합보다 작은 경우 특정 동전을 사용할 수 있다
- 이런 경우에 해당 dp값을 구하려면 직전 동전에서 구할 수 있는 경우의 수를 열 배열에서 해당 동전의 값을 빼준 곳의 dp값과 더한다
- 예를 들어, 1원, 2원의 동전을 사용할 수 있을 때, 총 4원의 가치의 합의 경우의 수를 구하는 방법 :
- 1원으로 4원의 가치의 합을 구하는 경우의 수 + 1원,2원으로 2원의 가치의 합을 구하는 경우의 수
numArray[i][j] = numArray[i-1][j] + numArray[i][j-coin[i-1]]
를 해준다
- 주의할 점!
swift에서는 배열의 원소가 swift에서 다룰 수 있는 Int형의 최대 값보다 커질 경우, 오버플로우 런타임 에러가 발생하므로 그러한 경우를 사전에 방지해주어야 한다
swift가 다룰 수 있는 Int형의 범위 :
Int의 최대 값: 9223372036854775807, Int의 최소 값: -9223372036854775808 (-2^31 ~ 2^31-1)
for i in 1...n {
for j in 1...k {
//i에 해당하는 동전을 사용할 수 있을 때 -> 해당 동전의 가치가 구하려는 총 동전의 가치 합보다 작을 때
if j >= coin[i-1] {
//배열의 원소가 swift에서 다룰 수 있는 Int형의 최대 값보다 커질 경우, 오버플로우 런타임 에러가 발생하므로
//다음과 같이 방지해주었다
if numArray[i-1][j] + numArray[i][j-coin[i-1]] >= Int(pow(2.0, 31.0)){
numArray[i][j] = 0
}
//해당 값의 dp를 구하려면 직전 동전까지의 가치 합 경우의 수에 해당 항목에서 해당 동전의 값을 뺀 값을 더한다
else {
numArray[i][j] = numArray[i-1][j] + numArray[i][j-coin[i-1]]
}
}
//i에 해당하는 동전을 사용할 수 없을 때 -> 해당 동전의 가치가 구하려는 총 동전의 가치 합보다 클 때
else {
numArray[i][j] = numArray[i-1][j]
}
}
}
전체 코드
import Foundation
let N = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n,k) = (N[0], N[1])
var numArray : [[Int]] = Array(repeating: Array(repeating: 0, count: k+1), count: n+1)
var coin : [Int] = []
for i in 0..<n {
coin.append(Int(readLine()!)!)
}
for i in 0..<n {
numArray[i+1][0] = 1
}
for i in 1...n {
for j in 1...k {
if j >= coin[i-1] {
if numArray[i-1][j] + numArray[i][j-coin[i-1]] >= Int(pow(2.0, 31.0)){
numArray[i][j] = 0
}else{
numArray[i][j] = numArray[i-1][j] + numArray[i][j-coin[i-1]]
}
}
else {
numArray[i][j] = numArray[i-1][j]
}
}
}
print(numArray[n][numArray[n].endIndex-1])