2839: 설탕 배달 (greedy 풀이)

[minsoo0715]

2839: 설탕 배달

소스 코드

아이디어

이 문제는 5kg, 3kg 봉지만 존재하므로, 남김없이 가져가는 경우 중에서, 5kg 봉지가 최대가 될 때 봉지의 개수는 최솟값을 가짐.
따라서 설탕을 최대로 가져갈 수 있는 5kg 봉지의 개수 구해서 이 값을 하나씩 줄여나가면서, 3kg 봉지로 남김없이 가져갈 수 있을 때, 봉지의 개수가 정답임.

구현

단순히 인덱스i를 N/5를 초기값으로 설정하고(최대한의 5kg 봉지 갯수)
N - i * 5가 3으로 나누어떨어질 때 까지 i를 줄여나가면서 설탕봉지의 최소값을 구할 수 있음.
만약 이 값을 찾지 못하면 -1 반환.

for(int i = N/5; i>=0; --i) {
    if((N - i*5) % 3 == 0) {
        cout << (N - i * 5) / 3 + i;
        return 0;
    }
}
cout << -1;