2839)설탕 배달

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

이 문제 예제만 보면 3으로 먼저 나누고 그 나머지를 5로 나누어 풀면 되겠다는 느낌을 받았다.

마지막 예제를 보면 입력이 11일 때 최소 봉지의 수가 3이 나와야 한다.

3kg 설탕 봉지가 2개, 5kg 설탕 봉지가 1개여야 가능하다.

3으로 먼저 나누고 그 나머지를 5로 나누든 5로 먼저 나누고 그 나머지를 3으로 나누든, 단순하게 나눠서 얻을 수 없는 조합이다.

설탕이 Nkg일 때 5kg 설탕봉지 a개와 과 3kg 설탕 봉지 b개로 나타낼 수 있다.

N = 5*b + 3*a (a,b는 정수)

식을 바꿔서 a에 대한 b의 함수로 나타낼 수 있다.

b = (N-3*a)/3

여기서 a를 0부터 b가 음수가 되기 전까지 하나 씩 값을 올려가면 언젠가 b가 정수가 되는 경우가 있을 것이다.

그때 a+b 값을 킵하고 그 중 최소인 a+b값을 출력하면 된다.

b가 실수값을 저장하기 때문에 정수일 때 정수인지 실수인지 판단해야 한다.

b의 소수부가 0이 아니라면 b에서 정수부를 뺐을 때 소수부는 0보다 커야 한다.

b-(int)b>0 이렇게 정수인지 실수인지 판단하면 된당.

#include<stdio.h>
#define NOT_CHANGED 5001
 
int main() {
    int N;
    int a = 0;
    double b = 0.0;
    int min = NOT_CHANGED;
    int tempSum;
 
    scanf("%d",&N);
    for (a = 0; b >= 0;a++) {
        b = (N - 5 * a) / 3.0;
        if (!(b-(int)b>0) && b>=0) {
            tempSum = a + (int)b;
            if (min>tempSum) {
                min = tempSum;
            }
        }
    }
 
    if (min!=NOT_CHANGED) printf("%d\n", min);
    else printf("-1\n");
 
    system("pause");
    return 0;
}