컴공댕이 공부일지
[ C++/cpp ] 백준 (2839 설탕 배달) ⭐그리디 알고리즘 본문
백준 2839번 설탕 배달
( 실버 4 )
https://www.acmicpc.net/problem/2839
2839번: 설탕 배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그
www.acmicpc.net
(정답 코드)
#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 봉지를 최대한 적게 써야한다 !
👇그리디 알고리즘에 관해 더 자세히 공부해보기 👇
[ 탐욕법 ] 그리디 알고리즘의 사용 조건 및 정당성 증명, 예시 문제 풀이
🔎 그리디 알고리즘(탐욕법)이란? 전체 문제를 여러 조각으로 분할하고, 각 단계별 최적해를 결합해 최종 최적 해를 만들어가는 알고리즘인데, 쪼갠 작은 단계마다 욕심쟁이처럼, 미래는 보지
somde.tistory.com
📝 나의 풀이 상세
그래서 나는 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를 빼는 것보다 효율적이라고 볼 수 있겠다 !
'문제 풀이 > 코딩 문제 풀이 모음' 카테고리의 다른 글
[ C++/cpp ] 백준 (2108 통계학) ⭐최빈값 구하기, 최장 길이 부분 수열 (0) | 2024.07.11 |
---|---|
[ C++/cpp ] 백준 (1018 체스판 다시 칠하기) ⭐브루트포스 알고리즘 (1) | 2024.03.29 |
[ C++/cpp ] 백준 (11268 절댓값 힙) ⭐자료구조, 우선순위 큐 (0) | 2024.03.28 |
[ C++/cpp ] 백준 (2840 행운의 바퀴) ⭐구현, 시뮬레이션 💥💦 (4) | 2024.03.05 |
[ C++/cpp ] 백준 (10814 나이순 정렬) ⭐sort_stable (0) | 2024.03.02 |