백준 2839 (그리디)

2839번: 설탕 배달

과정

• N은 3 * a + 5 * b로 이루어진 수이다.
• 가장 적은 봉지를 들고 가고 싶다고 했으니까, 5kg봉지를 최대한 들고, 남은 양을 3kg봉지로 채워야 한다.
• 음... 그럼 예를 들어서 15kg이 있으면, 5로 미리 나눠보면 이게 3봉지만 필요하다는게 바로 나오니까?
  N을 5로 먼저 나눠보고, 안나눠지면 -3해서 3kg봉지 1개 만들고 이런식으로 하면 될거같다.
  (모래성 깃발놀이 할 때 처음에는 크게크게 가져가다가 갈수록 적게 가져가는 것처럼)

→ 정답

 

찾아보니 이런 방식은 그리디(greedy), 탐욕법이었다.(어쩐지 너무 익숙했다)

이외에도 DP를 사용해서 풀 수 있는데, DP너무 어려움 DP문제는 내일 풀어봐야겠다.

 

코드

#include <iostream>

using namespace std;

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);

    int sugarNum = 0;   // 설탕 총 kg

    int answer = 0;     // 총 봉지 개수

    cin >> sugarNum;

    while(sugarNum >= 0)

    {

        if(sugarNum % 5 == 0)

        {

            answer += sugarNum / 5;

            cout << answer;

            return 0;

        }

        else

        {

            sugarNum -= 3;

            answer++;

        }

    }

    cout << -1;

}