[ C++/cpp ] 백준 (2839 설탕 배달) ⭐그리디 알고리즘

 

백준 2839번 설탕 배달

( 실버 4 )

 

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

2839번: 설탕 배달

 

 

 

(정답 코드)

#include <iostream>

using namespace std;

int sugarDelivery(int n) {
    
    int last3mul = -1 ; // 5를 빼며 나온 3 배수 저장
    int ans = 0;
    int copy_n = n;
    
    // 5로 나누어떨어지는 경우 5로 나눈 몫 바로 return
    if(n%5==0) {
        return n/5;
    }
    
    // 봉지 갯수를 줄이기 위해 3짜리는 최대한 적게, 5짜리는 최대한 많이 써야하므로,
    // 5 빼면서 나온 가장 작은 3의 배수가 최종 저장되도록 함.
    while (n>0) {
        
        
        if(n%3==0) {
            last3mul = n;
        }
        
        n-=5;
    }    
    
    if(last3mul == -1 ) { // 5 빼며 나온 3의 배수가 없다면, 만들 수 없는 무게 !
        return -1;
    } else {
        ans = (copy_n - last3mul)/5 + last3mul/3; // 5설탕 봉지 + 3설탕 봉지 갯수
        return ans;
    }
}




int main()
{

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n;
    cin >> n;
    
    cout << sugarDelivery(n);
    
    
    return 0;
}

 

 

📖 그리디 알고리즘의 적용

그리디 알고리즘을 활용하는 문제이다 !

 

1. 탐욕 선택 속성

최소한의 설탕 봉지를 쓰기 위해선 단순히 탐욕적으로 무거운 봉지를 우선적으로 고르면 된다 ! 

부분 문제의 그리디한 접근이 그 어떤 다른 부분 문제의 훼손과 손해 없이 안전하게 최종 정답으로 연결되기에 탐욕 선택 속성을 만족한다.

 

2. 최적 부분 조건

매 순간마다 최대한 무거운 봉지를 탐욕스럽게 취하다보면, 가장 적은 설탕봉지를 쓰게된다. 부분 문제의 최적해가 결합하면, 전체 문제의 최적해로 확장되므로 최적 부분 조건을 만족한다.

 

따라서 이 문제는 그리디 알고리즘을 활용하여 최적해를 구할 수 있는 문제이다 :)

 

탐욕법을 기반으로 문제를 풀어보쟈

단순히 말하자면, 최대한 적은 봉지를 쓰기 위해선 5kg 봉지를 최대한 많이, 3kg 봉지를 최대한 적게 써야한다 !

 

 

 

👇그리디 알고리즘에 관해 더 자세히 공부해보기 👇

https://somde.tistory.com/180

[ 탐욕법 ] 그리디 알고리즘의 사용 조건 및 정당성 증명, 예시 문제 풀이

 

 

 

📝 나의 풀이 상세 

 

그래서 나는 5씩 빼면서 3의 배수가 나오는 순간마다 기록을 했다.

그렇게 n이 0 이상인 동안 그 과정을 반복하면, 가장 작은 3의 배수를 얻을 수 있다.

 

매 순간 가장 작은 3의 배수를 기록해두고, 그 때를 기준으로 3kg 봉지 갯수와 5kg 봉지 갯수를 결정했다 :)

 

이 과정에서 3의 배수도, 5의 배수도, 5를 빼며 3의 배수를 얻을 수도 없는 경우는 -1이 출력된다 :)

 

 

 

 

 

 

+ 보다 깔끔한 다른 분의 풀이 추가

 

출처 : https://reakwon.tistory.com/126

#include <iostream>

using namespace std;

int N;
int main() {
	cin >> N;
	int ans = 0;
	while (N>=0) {
		if (N % 5 == 0) {	//가장 큰 수로 나누는게 가장 작은수랑 섞어서 나누는 것보다 유리
			ans += (N / 5);	//나눈 몫을 더한 것이 정답
			cout << ans << endl;
			return 0;
		}
		N -= 3;	//3kg을 빼고 
		ans++;	//가방 하나 늘어남
	}
	cout << -1 << endl;
}

 

 

이것도 똑같은 그리디 알고리즘을 활용한 풀이지만,

나보다 조금 더 깔끔한 방식이다 !

 

나는 5kg 봉지에 집중하며 최대한 3kg를 적게 쓰기위해서,

5를 빼며 3배수 중 min 값을 찾았는데, 이 풀이는 5의 배수가 나올때까지 3을 뺀다. 5의 배수가 나오자마자 그 몫을 취한다.

거의 똑같지만,, 가독성 측면에서 이 방식이 더욱 깔끔한 것 같다 :)

 

찬찬히 생각해보니, 5 봉지 갯수를 최대로, 3봉지 갯수를 최소로 만들어야하니

일반적으로 3을 빼는 것이 5를 빼는 것보다 효율적이라고 볼 수 있겠다 !