[백준] 2839 설탕 배달

문제 : 설탕봉지는 3kg과 5kg 봉투가 있습니다. 설탕을 배달할 때에 정확히 n kg 배달해야 하고, 최대한 적은 봉투를 써야합니다.

예를들어, 18kg 의 설탕을 배달할 때에 3kg 6개를 들고가도 되지만 5kg 3개와 3kg 1개를 들고가면 적은 봉투로 배달이 가능합니다.

또한, 4kg 같이 3kg봉투와 5kg봉투로 꽉 채우지 못하거나 남는 경우에는 배달이 불가능합니다. 이 때는 -1을 출력합니다. 

이 때, n kg의 설탕을 배달할 때 최소로 필요한 봉투의 개수를 출력하세요.

나의 접근법은 이러하다. (내 생각도 중요하지만 당신의 생각도 중요합니다. 내가 무조건 정답은 아닙니다.)

 n이 5의 배수일경우엔 n/5를 출력하면 된다. 5kg의 봉투로 다 담아서 배달하면 가장 최소가 되기 때문이다. 괜히 3kg의 봉투에 넣어 줄 필요는 없다.

하지만 n이 3의 배수라고 무조건 3의 배수를 출력하면 안 된다. 18 같은 반례가 있기 때문이다.

18 : 3x6 도 가능하지만 5x3 + 3x1 로도 나타낼수 있기 떄문이다. 그렇게 되면 답은 4가 나온다.

간단히 방정식을 세워보자. n=3x + 5y 라고 나타낼 수 있다.

y를 0부터 (5y<n) 이 될때까지 0부터 세보면, x가 최소일 경우가 있을 것이다. (단, x는 정수)

그 x가 최소인 경우와 그 때의 y의 합을 출력하면 답이 나온다.

#include <stdio.h>
 
int main(void)
{
    int input,n3=0,i5=0,n5=0;
    scanf("%d",&input);
    
    if(input%5==0)
    {
        printf("%d",input/5);
        return 0;    
    } 
    
    while(input>=5*i5)
    {
        if(((input-5*i5)%3)==0)
        {
            n3=(input-5*i5)/3;
            n5=i5;
        }
        i5++;
    }
    
    if(n3==0) printf("-1");
    else printf("%d",n5+n3);
    
    return 0;
}