BOJ. 2839

#BOJ2839

설탕 배달

이 문제는 그리디 알고리즘을 사용해서 해결할 수 있는 문제이다. 알고리즘들에 대해서 공부하다 보면 생소한 용어가 많이 나오는데 이해하고 보면 아주 단순한 생각들이 많다. 이 그리디 알고리즘도 말 그대로 그 순간의 최적의 선택만을 진행하는 것이다. 아래 그림이 참고하기에 좋을 것 같아서 가져왔다.

다음과 같이 그 순간의 최적의 선택만을 진행하는 것이 그리디 알고리즘인데 이 문제를 해결하는 과정에서 그리디 알고리즘이 사용된다. 내가 구현한 알고리즘에서도 동일한 과정을 살펴볼 수 있는데 문항에서도 최대한 5개를 빼는 방향으로만 적용하면 정답에 접근할 수 있다.

# include "iostream"
using namespace std;

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