[바미] 설탕 배달 다국어

문제

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

코드 

function minBagsOfSugar(N) {
    let fiveKgBags = Math.floor(N / 5); // 가능한 한 많은 5kg 봉지 수
    let remainingWeight = N % 5;       // 5kg 봉지 사용 후 남은 무게

    while (fiveKgBags >= 0) {
        if (remainingWeight % 3 === 0) { // 남은 무게가 3kg 봉지로 딱 맞을 경우
            return fiveKgBags + (remainingWeight / 3); // 5kg 봉지 수 + 3kg 봉지 수
        }
        fiveKgBags--; // 5kg 봉지 한 개를 줄이고 다시 시도
        remainingWeight += 5; // 줄인 5kg 봉지만큼 무게를 다시 더함
    }

    return -1; // 정확하게 N kg을 만들 수 없는 경우
}

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const N = parseInt(input, 10);
console.log(minBagsOfSugar(N));

코드 설명

• minBagsOfSugar 함수는 설탕 무게 N을 인자로 받아 최소 봉지 수를 계산하는 함수.
• fiveKgBags는 가능한 한 많은 5kg 봉지를 사용하는 초기 값.
• remainingWeight는 5kg 봉지를 사용한 후 남은 무게.

while 루프 내에서, 남은 무게가 3kg 봉지로 정확히 나누어 떨어지면 총 봉지 수를 계산하여 반환해줍니다.

만약 나누어 떨어지지 않는다면, 5kg 봉지의 수를 하나 줄이고 남은 무게를 조정한 후 계속 검사하고, 모든 가능성을 검토한 후에도 정확한 무게를 만들 수 없다면 -1을 반환하는 형태입니다.

문제 풀이

먼저, 5킬로그램 봉지를 최대한 많이 사용하는 전략을 사용하여 풀어보았습니다.

이후 남은 무게를 3킬로그램 봉지로 채울 수 있는지 확인하고, 만약 정확하게 채울 수 없다면 5킬로그램 봉지의 수를 줄이면서 다시 시도하는 방식이죠.

 

이 방식은 5킬로그램 봉지를 최대한 활용하여 봉지의 수를 최소화하려는 전략입니다.

시간 복잡도

최악의 경우 5kg 봉지의 개수만큼 반복문이 실행되므로 0(N/5)가 됩니다.

공간 복잡도

상수 공간만 사용되기 때문에 0(1)이 됩니다.