모든 케이스를 다 해 보지 않는 이상 결론을 내리기 힘든 종류의 문제 해결은 동적 계획법(Dynamic Programming)으로 접근하는게 확률상 가장 적절합니다.

각 서브 루틴의 결과 값들을 구하여 최종 목적에 다다르는 프로그래밍 기법을 말하며 반복되는 서브루틴에서 얻은 값을 저장해서 재사용함으로써, 수행시간을 줄이는 것이 핵심입니다.

재귀를 사용하는 방식도 있고 일반적인 반복문을 돌면서 이전 작업을 기록하고 구해 나가는 방식도 있습니다. 혹은 둘 다 사용될 수도 있겠죠. 그리고 하나의 문제도 여러 방법으로 풀 수 있습니다. 다만 어떻게 구현하든 서브루틴, 값 재사용 이 DP의 핵심 이라는 것만 기억하시면 해결할 수 있습니다.

아래는 재귀를 활용한 pseudo-code 입니다.

input = 2.2

kgs = [1, 1.3, 1.6]
wons = [3000, 4000, 5000]

function getMinCost (target) {
    // input이 0일 경우 예외처리.
    // 함수 밖에서 미리 막아주면 필요 없다.
    if target == 0
        return 0

    minCost = INFINITY

    for (i = 0; i < kgs.length; i++) {
        rest = target - kgs[i]
        minCost = MIN(minCost, wons[i] + (rest > 0 ? getMinCost(rest) : 0))
    }

    return minCost
}

print getMinCost(input)

현재 위 코드는 최적화된 알고리즘이라고 부르기에는 부족합니다. DP문제 특성상 특수해가 없으므로 모든 경우의 수를 체크하게 되는데, 위 코드 또한 모든 케이스를 다루는데 그 초점이 맞춰져 있을 뿐 DP 특성을 활용한 묘리는 없으니까요.

target값을 기준으로한 메모이제이션을 활용하면 좀 더 효율적으로 답을 구할 수 있습니다. 그게 바로 DP의 핵심이기도 하고요.

메모이제이션은 스스로 구현하시리라 믿고 저는 이만...