문제 정보


image

풀이

다이나믹 프로그래밍

전체 문제의 최적해가 부분 문제의 최적해로부터 만들어지는 알고리즘이다

  • 하나의 문제를 단 한 번의 연산으로 해결하기 위해, 즉 전체 문제를 풀 때, 동일한 계산을 반복하지 않기 위해
  • Table에 부분문제의 solution을 저장한다
  • 항상 최적의 해를 보장하지만
  • Table에 부분문제의 solution을 저장하므로 많은 메모리를 차지한다

알고리즘 설계

아래의 그림과 같이 다이나믹 프로그래밍 배열을 하나 생성하여 부분 문제의 해에 해당하는 값들을 넣어주었다
i : 해당 동전까지 사용할 수 있을 때 만들 수 있는 경우의 수
j : 가치의 합을 1원부터 k원까지 만들 수 있는 경우의 수 라고 설정하였다
예를 들어 i = 2, j = 5일 때 해당 배열 numArray[2][5] 에는, 동전을 1원짜리랑, 2원 짜리 두 개를 사용할 수 있을 때, 5원을 만들 수 있는 경우의 수가 들어간다
이렇게 모든 배열을 다 채운 후, 가장 마지막 원소를 출력하면 그 값이 1원, 2원, 5원 총 3개의 동전으로 10원을 만들 수 있는 경우의 수가 나온다
image 이러한 배열을 채울 때 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])