백준 2839번(그리디)

2839번(그리디)

마치 잔돈 문제와 매우 유사한 구조의 문제였습니다. 3과 5를 최소한으로 사용하여 N을 만들어야했고 만들 수 없을 때는 -1을 리턴해야했습니다. 분기를 최대한 나누는 방식으로 문제를 해결했습니다. 일단 가장 큰 수인 5로 나누었고(-> 이 몫을 fiveShare라고 했습니다.) 그 값을 기준으로 분기를 나눴습니다. 5로 일단 나눈 뒤, 남은 숫자를 3으로 나누어질때까지 fiveShare의 값을 1씩 빼면서 반복해서 진행하는 것이 핵심 아이디어였습니다.

#include <stdio.h>

int getMinNum(int n) {
	int fiveShare = n / 5;

	if (fiveShare == 0) {
		if ((n % 3) == 0) {
			return 1;
		}
		return -1;
	}

	if ((n % 5) == 0) {
		return fiveShare;
	}
	else {
		int remainder = n % 5;
		while ((remainder % 3) != 0) {
			fiveShare--;
			if (fiveShare < 0) {
				return -1;
			}
			remainder = n - 5 * fiveShare;
		}
		int threeShare = remainder / 3;
		return fiveShare + threeShare;
	}
}

int main() {
	int n; // N kg
	int num; // 봉지수

	scanf_s("%d", &n);
	num = getMinNum(n);
	printf("%d", num);

	return 0;
}