https://www.acmicpc.net/problem/2839
문제
> 설탕을 N킬로 배달해야한다.봉지는 3키로, 5킬로 존재함.
> 18킬로면 3킬로 6개가 아닌 5킬로 3개 3킬로 한개 이렇게 최대한 적은 봉지 배달하려함.
> 정확히 N킬로 못만들면 -1 출력접근
이 문제는 동전 거스름돈 문제와 비슷한 양상의 문제이므로 그리디 알고리즘을 사용했다.
그리디 알고리즘
"매 선택에서 지금 이 순간 최적인 답을 선택하여 적합한 결과를 도출하자"라는 알고리즘이다.
"탐욕 선택 속성", "최적 부분 구조" 특성을 가지는 문제들을 해결하는데 강점이 있다.
대표적인 예시로 "동전 거스름돈 문제"가 있다.
문제해결
> 5킬로 봉지만으로 N을 해결할 수 있을 때가 최적의 답이므로 5로 다 담았을 때 나머지가 없는지 본다.
없다면 봉지 수(cnt)를 출력한다.
> 5킬로만으로 해결이 안된다면 3킬로 봉지를 하나씩 추가(N에서 3씩 뺸다.)하며 봉지를 1봉지씩 누적한다.
> 일단 5킬로로 해결되나 보고 안되면 3킬로씩 빼는 과정을 반복하며 최적의 답을 찾는다.코드
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
int cnt = 0;
while (N >= 0)
{
if (N % 5 == 0)
{
cnt += N / 5;
cout << cnt << '\n';
return 0;
}
N -= 3;
cnt++;
}
cout << -1 << '\n';
}
후기
처음에 풀었을때 완전 탐색 방식으로 5킬로가 0봉지 일 떄부터 모든 경우를 돌며 그 중 가장 적은 봉지를 사용한 경우를 저장했다가 마지막에 출력하는 방법을 사용했다.
하지만 그리디를 사용하면 최적의 답부터 시도하기 때문에 불필요한 연산을 줄일 수 있고, 코드도 짧아지고, 메모리 효율성도 좋아진다는걸 공부했다.
알고리즘 공부도 병행하자.
