이 문제를 어떤 알고리즘으로 풀어야할지..

조회수 79회

문제가 a b c라는 3개의 상자가 있는데 a는 1kg을 담을수있는상자 b는 1.3kg을 담을수 있는상자 c는 1.6kg을 담을수 있는 상자다. 이때 a,b,c 상자의 각각 값은 3000원 ,4000원,5000원이다. 이때 사과 2.2kg(예시 임의의 무게)을 a,b,c상자를 사용하여 사과들을 담아야할때 각 박스를 얼만큼 사용하여야 최소비용이 나오는지 구하여라 인데 어떻게 접근해야할까요..

백준이나 프로그래머스문제는아니고 회사에서 프로그램을 짜야하는데 딱해답이 안떠오르네요

  • 상자 3개의 1kg당 가격은 1kg짜리가 가장 싼데 전부 1kg 상자에 담고 마지막에 1kg 상자 2개를 1.3kg 상자나 1.6kg 상자 하나로 바꿀 수 있는지만 확인하면 되지 않을까요? HIAOAIH 2020.3.20 18:23
  • 질문하신 문제가 일명 '배낭 문제'라고 보이네요. 유사한 문제(https://www.acmicpc.net/problem/4781) 입니다. 한번 공부해보시길 추천드립니다. 겨털에뽀뽀 2020.3.21 21:56

1 답변

  • 모든 케이스를 다 해 보지 않는 이상 결론을 내리기 힘든 종류의 문제 해결은 동적 계획법(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의 핵심이기도 하고요.

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

답변을 하려면 로그인이 필요합니다.

Hashcode는 개발자들을 위한 무료 QnA 사이트입니다. 계정을 생성하셔야만 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 계정을 생성하셔야만 글을 작성하실 수 있습니다.