2839. 설탕 배달

---

1. 올바른 풀이

2. 깔끔한 Solution

3. 나의 Solution

---

그리디 문제이다.

(선택의 순간마다 당장의 눈 앞에 보이는 최적의 선택을 함)

 

1. 올바른 풀이

최소의 설탕봉지를 선택해야 한다.

필자는 이 문제를 해결하기 위해 "모든 경우의 수를 탐색해야 한다"에만 초점을 맞추어 잘못된 문제 풀이를 했다.

필자가 생각하는 올바른 문제 풀이는 "탐욕적으로 선택하기"이다.

 

그렇다면, 설탕봉지 문제에서 탐욕적인 선택은 "5kg 설탕봉지부터 가지기"이다.

예시로 30Kg 설탕봉지는 5kg 만으로 가져가면 6개의 설탕봉지를 배달하고, 3kg 만으로 가져가면 10개의 설탕봉지를 배달한다.

 

2. 깔끔한 Solution

알고리즘 문제를 풀 때, 깔끔한 코드를 보며 배우는 것은 중요하다고 생각한다.

아래의 코드의 장점은 짧은코드라인이다.

필자는 이러한 알고리즘 아이디어를 배우고 싶기 때문에 기록한다..!

 

#include <iostream>
using namespace std;

int main() {
	int N;
	int count = 0;


	cin >> N;

	
	while (N>=0) {

		if (N % 5 == 0) {
			count += N / 5;
			cout << count;
			
			return 0;
		}

		N -= 3;
		count++;
	}
    
	cout << "-1";
}

 

3. 나의 Solution

// 백준 2839 설탕 배달

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Deliver(int N)
{
    int n, m;   // 3kg, 5kg
    int MAXm = N / 5;

    for(m = MAXm; m >= 0; m--)
    {
        if((N - 5 * m) % 3 != 0) continue;
        else
        {
            n = (N - 5 * m) / 3;
            return m + n;
        }
    }

    return -1;
}


int main()
{
    int N;
    cin >> N;
    cout << Deliver(N) << endl;

    return 0;
}