[C]백준 08.기본수학1: 2839

백준 2839

내코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int n;
	scanf("%d", &n);
	int result;
	int max_a = n / 5;
	int a = 0;
	int b = -1;
	if (n % 5 == 0) {
		a = max_a;
		b = 0;
	}
	else {
		for (int i = max_a; i >= 0; i--) {
			if ((n - 5 * i) % 3 == 0) {
				a = i;
				b = (n - 5 * i) / 3;
				break;
			}
		}
	}
	result = a + b;
	printf("%d", result);

	return 0;
}

a를 5kg 봉지의 수, b를 3kg 봉지의 수라고 생각하고 문제를 풀었다. 5a+3b=n을 만족하면서 a+b를 최소화시키려면 5kg 봉지를 많이 들고갈수록 전체적으로는 더 적은 봉지를 가져갈 수 있다고 생각했다. 그래서 a가 될 수 있는 최대값을 기준으로 그 값을 줄여가며 n=5a+3b를 만족시키는 지 확인했다. a가 될 수 있는 최대값은 n/5이다. 만약 임의의 수 i가 있을 때 n-5i가 3으로 나누어 떨어진다면 5i+3(n-5i)=n을 만족할 것이다. 그래서 i를 a가 될 수 있는 최대값인 n/5부터 0까지 감소하며 위의 조건을 만족하는지 확인하여 문제를 풀었다.

다른 사람의 코드를 찾아보니 더 간단한 코드를 발견했다. n이 5의 배수인지 확인하여 배수라면 몫을 결과에 더해주고, 아니라면 3을 빼고 결과에 1을 더한 후 반복문을 통해 반복하는 코드이다. 탈출조건은 n이 0이하일때이다. 만약 n이 0보다 작다면 정확하게 n킬로그램을 만들 수 없는 경우이기에 -1을 출력하고 그 외엔 결과값을 출력한다. 아래는 그 코드이다. 

#include <stdio.h>
 
int main() {
    int N, cnt = 0;
    scanf("%d", &N);
    
    while (1) {
        if (N % 5 == 0) {
            cnt += N / 5;
            break;
        }
 
        N -= 3;
        cnt++;
        if (N <= 0) break;
    }
 
    if (N < 0) printf("-1\n");
    else printf("%d\n", cnt);
}