알고리즘 - 쌀배달

알고리즘 - 쌀 배달

 

문제 설명

쌀 가게에 정확하게 N 킬로그램 배달해야 한다.
가진 쌀 포대는 3킬로와 5킬로 포대가 있다.
최대한 적은 봉지 개수로 배달을 하려한다. 
예를 들면, 21킬로그램 쌀은, 3킬로 포대 7개로 배달 가능 하지만, 
5킬로 3포대와 3킬로 2포대로 배달하면 총 5포대로 더 적은 개수로 배달할 수 있다.
쌀을 N킬로그램 배달할 때, 가장 적은 쌀 포대의 개수를 구하는 프로그램을 작성하세요.
- 정수 N이 주어진다. (3 ≤ N ≤ 1,000)
- 정확하게 N킬로그램을 만들 수 없다면 -1을 출력

 

const n = 18

function delivery(n){
    let count = 0
    while(n > 2){
        if(n % 5 === 0){
            return count += parseInt(n / 5)
        }else{
            n = n - 3
            count++
        }
    }
    return n === 0 ? count : -1
}

console.log(delivery(n))

 

최대한 적은 경로를 먼저 실행하고

떨어지지 않으면 그 다음 경로를 실행한 후 다시 최적 경로를 실행하는 방식으로 구현.

 

 

응용 문제 : 백준 설탕배달 https://www.acmicpc.net/problem/2839