2839번

2839번 - 설탕 배달

5kg 짜리 설탕봉지를 최대한 많이 사용할 수록, 전체 사용 갯수는 줄어든다.

N제한이 최대 5000이기 때문에, 최소 봉지 사용 갯수가 1000개, 최대 봉지 사용 갯수는 1666개가 되므로 충분히 시간내에 풀 수 있다.

따라서 재귀함수를 5kg 을 먼저 사용하도록 돌리면서, 정답이 나오면 프로그램을 종료한다.

하지만 만약 정답이 나오지 않으면 -1을 출력한다.

<정답 코드>

#include<iostream>
 
using namespace std;
int N;
void go(int n,int k)
{
    int ret = 0;
 
    if (n == N)
    {
        cout << k << "\n";
        exit(0);
        return ;
    }
    
    if (n > N)
    {
        return ;
    }
 
    go(n + 5,k+1);
    go(n + 3,k+1);
 
 
 
    
 
}
int main()
{
    cin >> N;
 
    go(0,0);
 
    cout << "-1\n";
    return 0;
 
}