[BaekJoon 2839][⚪4] 설탕 배달
❓ 문제
🎯 난이도
Silver ⚪4
🧠 풀이
1. 내 풀이 (그리디)
- 알고리즘
Greedy
- 설명
그리디 알고리즘을 사용해서 푼 풀이이다.
- 최대 / 최소를 구해야 한다.
- 큰 단위부터 정렬해야 한다는 확실한 기준 존재한다.
- 선택을 되돌릴 필요가 없다.
- 매 순간 하나를 선택하는 구조이다.
위 같은 조건을 만족하는 문제이므로, 그리디 알고리즘을 쓰면 딱 좋은 문제이다. 게다가 봉지 종류가 2종류에 무게가 서로소이므로 중복되는 해나 반례도 존재하지 않으므로 확실하다.
원리는 간단하다. '5kg'를 최대한 많이 쓴다는 가정하에 반복문을 시작해서, 나머지를 '3kg'으로 딱 떨어지게 나눌 수 있는지를 구하면 된다.
하나의 반복문만 존재하므로 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
// 5의 최대 갯수부터 시작
for(int i = iN / 5; i >= 0; --i)
{
int iRemain{ iN - 5 * i };
// 나머지가 3의 배수로 딱 떨어질 때 출력
if(iRemain % 3 == 0)
{
cout << i + iRemain / 3;
return 0;
}
}
cout << -1;
return 0;
}
2. 추가 풀이 1 (그리디)
- 알고리즘
Greedy
- 설명
또 다른 방식의 그리디 알고리즘을 사용한 풀이이다.
위와 같은 그리디 알고리즘을 사용한 풀이이지만, 기준을 조금 바꾼 방식이다. '3kg'의 갯수를 늘려가며, 나머지를 '5kg'로 딱 떨어지게 나눌 수 있는지를 구하는 풀이로, 위와 완전히 반대되는 조건으로 풀었다고 보면 된다.
위의 풀이와 마찬가지로 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
int iThree{}; // 3의 갯수
// 3의 갯수를 늘려가며 5로 딱 떨어지는 때가 있는지 확인
while(iN >= 0)
{
// 나머지가 5로 딱 떨어질 때 출력
if(iN % 5 == 0)
{
cout << iThree + iN / 5;
return 0;
}
iN -= 3;
++iThree;
}
cout << -1;
return 0;
}
3. 추가 풀이 2 (DP)
- 알고리즘
Dynamic Programming
- 설명
DP 알고리즘을 사용한 풀이이다.
모든 그리디는 DP로 대체될 수 있으므로, 이번 문제 또한 DP를 사용한 풀이가 가능하다. 루프를 돌며 매번 마지막 한 개가 '3kg', '5kg'일 때의 그 순간의 최적해를 구하는 방식으로 점화식을 만들면 된다. 점화식은 다음과 같다.
\[dp[n] = \text{n kg 을 만들기 위한 최소 봉지 수}\] \[dp[n] = min(dp[n - 3], dp[n - 5]) + 1\]
위의 점화식을 토대로 알맞게 코드를 짜면 끝이다.
DP를 사용하더라도 마찬가지로 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
constexpr int INF = 1e9;
int iN{};
cin >> iN;
int arrDP[5001]{};
fill(arrDP, arrDP + 5001, INF); // 0 빼고 다 INF로 초기화
arrDP[0] = 0;
for(int i = 3; i <= iN; ++i)
{
if(i >= 3) // i번째 배열이랑 (3kg 뺀 배열 + 1) 중에 작은거
{
arrDP[i] = min(arrDP[i], arrDP[i - 3] + 1);
}
if(i >= 5) // i번째 배열이랑 (5kg 뺀 배열 + 1) 중에 작은거
{
arrDP[i] = min(arrDP[i], arrDP[i - 5] + 1);
}
}
cout << (arrDP[iN] == INF ? -1 : arrDP[iN]);
return 0;
}
💭 후기
그리디를 사용한 풀이 2가지, DP를 사용한 풀이 1가지를 정리해 보았다. 각각의 장단점은 있겠지만, 첫 번째 풀이가 가장 최적 풀이라 생각이 되고, 그 이유는 다음과 같다.
- 첫 번째 풀이 :
5kg을 최대로 잡고 나머지에서3kg을 구하므로 반복이 최대N / 5번이다. - 두 번째 풀이 :
3kg를 하나씩 늘려가며 나머지에서5kg을 구하므로 반복이 최대N / 5번이다. - 세 번째 풀이 :
Nkg까지의 모든 최적해를 구하므로 반복은N번이다.
하지만 다른 풀이들도 알아 놓으면 나쁠 건 없다! 또한 모든 그리디는 DP로 가능하다는 것을 기억하자.
Comments