[백준] 11047 (동전 0)

#1 알고리즘

#1-1 그리디 알고리즘을 적용할 수 있는가?

그리디 알고리즘 (Greedy Algorithm)

위와 같은 그리디 알고리즘을 구현하면 일단 (정답인지 아닌진 몰라도) 일단 풀리긴할 것 같이 생긴 문제다. 하지만, 그리디 알고리즘을 적용할 수 있는 지에 대한 확신이 들지 않는다. 이 문제가 그리디 알고리즘임을 증명할 수 있다면, 마음 편히 그리디 알고리즘을 적용해 풀 수 있을테다. 따라서, 이 문제에서 최선의 선택이 곧 최적해가 되는 지의 여부를 증명해보겠다.
 

#1-2 그리디 알고리즘 증명

10000, 5000, 1000
a, b, c

동전의 종류를 내림차순으로 a, b, c, ...라고 치환해 생각한다. 그리고 모든 a, b, c, ...에 대해, n번째 동전은 n + 1번째 동전보다 반드시 2배 이상 크다 (문제에 있는 배수 조건)
 

(a * C_a)+ (b * C_b) + (c * C_c)= K

동전의 갯수를 C_a, C_b, C_c라고 두면, 위와 같은 식을 세울 수 있다. a, b, c는 불변이므로 프로그래머가 수열 C_a, C_b, C_c를 어떤 값으로 잡느냐가 이 문제 풀이의 핵심이 된다.

 

(a * 8) + (b * 7) + (c * 6) = K

예를 들어 C_a, C_b, C_a를 8, 7, 6로 두었다고 해보자. 이 경우 (정답으로서) 출력할 동전의 갯수는 8 + 7 + 6 = 21개다.

 

(a * 8) + (b * 7) + (c * 6) = K = (a * 7) + (b * ?) + (c * ?)

C_a를 1만큼 줄여보기로 한다. 이 때 C_a를 제외한 C_b, C_c에는 어떤 값을 넣어주어야 하는가? 확실한 것은 (정답으로서) 출력할 동전의 갯수는 반드시 (이전 값인) 21개를 초과할 것이라는 사실이다. a는 b보다 반드시 2배 이상의 값이며, b는 c보다 반드시 2배 이상의 값이다. 그러므로 a의 갯수(C_a)가 1만큼 줄면, 해당 손실을 채우기 위해서 b는 최소 2개 이상 그리고 c는 최소 4개 이상 투입되어야 하는 것이다.

 
따라서 이 문제의 최적해는 앞쪽 원소의 값이 큰 수열 C_a, C_b, C_c, ...다.
 

#2 여담

모든 프로그래밍에 수학적 센스가 요구되는 것은 아니지만, 하여튼 프로그래밍에 정통하려면 수학적인 능력은 거의 필수가 아닌가 싶다. 그렇다고 (기회비용 상) 수학 문제집을 풀 수는 없는 노릇이니, 평소에 수학적인(?) 생각을 잘 하면서 살아야겠다.
 

#3 코드 - 코틀린

var n = -1
var k = -1
lateinit var coinPrices: Array<Int> // 동전 가격을 내림차 순으로 넣을 것임
lateinit var coinCounts: Array<Int>

fun main() {
    // 초기화
    val nAndK = readln().split(" ")
    n = nAndK[0].toInt()
    k = nAndK[1].toInt()
    coinPrices = Array(n) { -1 }
    for (i: Int in (coinPrices.size - 1) downTo 0) {
        coinPrices[i] = readln().toInt()
    }

    // 그리디 알고리즘으로 coinCounts 계산
    coinCounts = Array(n) { 0 }
    for (i: Int in coinPrices.indices) {
        coinCounts[i] = k / coinPrices[i]
        k -= coinPrices[i] * coinCounts[i]

        if (k == 0) {
            break
        }
    }

    // 출력
    var totalCount = 0
    for (i: Int in coinCounts.indices) {
        totalCount += coinCounts[i]
    }
    println(totalCount)
}