[2839] 설탕 배달

백준 문제

내가 풀었던 방법

처음에는 dp로 나오는 숫자들의 규칙성을 찾아보려고 했지만, 11을 input으로 넣었을 때 반례가 발생해서 5로 나누었을 때가 최소의 경우이므로 5의 배수일 경우에는 본래 답에 5로 나눈 값을 더했다. 본래 수는 input값에서 3을 1번 뺀 후 그 횟수만큼 다시 더하였다.

#include<iostream>

using namespace std;

int main(){
	int n, ans=0;
	
	cin>>n;
	
	while(1){
		if(n%5==0){
			ans += n/5;
			cout<<ans;
			break;
		}
		n-=3;
		ans++;
		if(n<0){
			cout<<-1;
			break;
		}
	}
}

정답

그리디 알고리즘을 이용해 푸는 방법이었다.