그리디 알고리즘 > 설탕 배달 (2839번)

문제 설명

 

---

풀이

어렸을 때 자연수 조합인가? 해서 연립방정식 배울 떄 두 미지수의 값을 노가다로 대입하는 문제 알아?

그런거처럼 풀었어 ㅋㅋㅋㅋㅋ

5kg짜리가 많을수록 전체 봉지 수는 최소가 될테니까 최대 5kg 개수부터 시작해서 남은 무게가 3으로 나눠 떨어지면 바로 그게 답으로 출력, 아니면 5kg 봉지 수 하나 줄이고 또 3으로 나눠지는지 확인하기 반복했어

만약 반복문 끝나도 result가 -1이면 구할 수 없는 거니까!

생각보다 쉬워서 기분 좋아졌어!

그리디 3일만에 정복해줄게 딱 기다려

(일단 스터디 과제부터 내일 끝내자 제발,,ㅠㅠ)

---

코드 (C++)

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int n;
    int result=-1;
    cin >> n;
    
    int limit = n/5;
    for(int i=limit;i>=0;i--)
    {
        if((n-5*i)%3==0)
        {
            result=0;
            result+=i;
            result+=(n-5*i)/3;
            break;
        }
    }
    printf("%d\n",result);
    return 0;
}