[백준] 2839. 설탕 배달

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

Python

n = int(input())

num5 = n//5

while True:
    count = num5
    ret = n - num5*5

    if ret % 3 == 0 :
        count += ret//3
        print(count)
        break
    num5 -= 1
    if num5 < 0:
        print(-1)
        break

C++

#include <iostream>

using namespace std;

int main(void) {
	int n;
	cin >> n;

	int num5 = n / 5;
	int count, ret = 0;

	while (true) {
		count = num5;
		ret = n - num5 * 5;

		if (ret % 3 == 0) {
			count += ret / 3;
			cout << count;
			break;
		}

		num5 -= 1;

		if (num5 < 0) {
			cout << -1;
			break;

		}
	}


}

풀이

greedy algoritm 기초. 5kg 봉지를 우선으로 가져갈 수 있도록 하기 위해 5kg 봉지를 최대한으로 가져갈 수 있는 수를 num5에 저장한 뒤, 3kg 봉지를 몇개 가져갈 지 정한다.

while문을 돌며 5kg 봉지를 줄여나가며 답을 구할 수 있도록 한다.

가져갈 수 있는 5kg 봉지의 수가 -1, 즉 3kg 봉지를 모두 써도 설탕을 가져갈 수 없을 경우에 -1을 출력하고 break로 while문을 탈출한다.

​

C++는 0초가 걸리고 Python은 76ms가 걸린다.. 확실히 python이 느리다.