[BOJ] 2839. 설탕배달

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 10000001
typedef long long ll;
using namespace std;
int main(void)
{
	int num;
	int sum = 0;
	int cnt;
	scanf("%d",&num);
	
	cnt = num / 5;
	if(num % 5 != 0)
	{
		for(int i = cnt; i >= cnt; i--)//500원을 많이 쓸 수록 좋음 
		{
			if( (num-5*i) % 3 == 0)
			{
				sum += i + (num- 5*i) / 3;
				break;
			}
		}
	}else{
		printf("%d\n",num/5);
		return 0;
	}
	/*
	if(sum) printf("%d\n",sum);
	else printf("-1\n");
	*/
	printf("%d\n",sum == 0? -1 : sum);
    return 0;
}

---

풀이방법 :

5원이 많을수록 최솟값이 나오게 된다.

처음에는 5로 먼저 나누고 3으로 나누니까 6 같은곳에서 오류가 났다.

​

아무리 생각해도 하나하나 다 해봐야 했다.

그러면 1000이면 5일때, 10일때, 15일때, 20일때.. 다 할것인가?

그러면 너무 비효율 적이다. 바로바로 나눠지는것들은 버린다.

​

만약 36이라면?

36을 먼저 5로 나눠본다. 몫이 7이다.

일단 5로 나누어 떨어지면 무조건 최소니까 바로 출력하고, 그게 아닌경우는 저 7을 이용한다.

for문이 왜 7부터 시작인가?

개수의 최소를 찾으므로 5kg이 가장 많을때부터 찾아야하기 때문이다.

1. 5kg 7개 를 빼고 나머지가 3으로 나누어 떨어지는가를 검사한다.

만약 그렇게 되지 않으면 5kg을 하나 뺀다. i--

2. 5kg 6개를 빼고 3으로 나누어 떨어지는가? yes

그러면 정답에 5kg그람 개수(i)와 3kg그람 개수를 합한다.

​

만약 찾지 못한경우 ?

sum은 0일것이다.

따라서 printf에서 -1을 출력하면 된다.

​

그리디 방식이라고는 하는데.. 그냥 완전탐색급 아닌가? 쩝..

그럼 이만!!

​

==========END===============