[백준/C] 2839번 - 설탕 배달

주어진 무게를 5kg, 3kg 짜리 설탕 포대를 조합하여 맞추어야 하는데, 개수가 최소가 되도록 해야 한다.

 

즉, 5kg짜리 포대는 최대한 많이, 3kg짜리 포대는 최대한 적게 조합해야 한다.

 

따라서, 주어진 무게에서 3 씩 빼 가며 5로 나누어 보아 나누어 떨어지면 그 때 까지 뺀 3의 개수 + 5로 나누었을 때의 몫이 출력되도록 했다.

 

주어진 무게에서 0이 될 때 까지 3을 계속 빼다 보니 만약 훨씬 큰 무게가 주어진다면 시간초과가 뜰 것 같다.

 

좀 비효율적인 방법이다. 더 수학적으로 접근해 볼 필요가 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
    int weight, new_weight, num_3kg = 0;

    scanf("%d", &weight);

    new_weight = weight;

    while (new_weight >= 3) {
        new_weight = weight - 3*num_3kg;
        if (new_weight % 5 == 0) {
            printf("%d\n", new_weight / 5 + num_3kg);
            return 0;
        }
        num_3kg++;
    }

    printf("-1\n");

    return 0;
}