쌀 배달 그리디 알고리즘 | C++

안녕하세요. 혀코입니다.

이번 시간에는 최적의 값을 찾는 그리디 알고리즘에 대해서 알아보겠습니다.

 

쌀을 n kg 주문을 받아서 배달을 해주는 프로그램을 만든다고 가정해 보겠습니다.

쌀을 담은 포대가 5kg, 3kg 밖에 없을때, 최소한의 개수로 배달을 할 수 있게 최적의 개수를 찾는 알고리즘이 그리디 알고리즘 입니다.

만약 18kg을 주문받았다고 했을 때, 5kg 세개와 3kg 하나 이렇게 4개를 배달하면 되고,
6kg을 주문받았다고 했을 때는 3kg 2개를 배달하면 되고,
최적의 값을 찾지 못했을 때는 -1이 출력이 되어야 합니다.

우선, 가장 큰 값으로 n을 나눠줘야 합니다. 만약 나머지가 발생되면, n에서 작은값을 한번 빼주고 작은값을 뺀 값에서 다시 큰 값으로 n을 나눠주고 나머지가 남는지 확인해서 남지 않으면 몫값에 n에서 작은값을 빼준 횟수 만큼 더해서 출력해 주면 됩니다.

#include <iostream>

int main() {
    int n;
    scanf("%d", &n);
    if(n%5==0 && n>=0) {
      printf("%d", n/5);
      return 0;
    }
    n -=3;
    if(n%5==0 && n>=0) {
      printf("%d", n/5+1);
      return 0;
    }
    n -=3;
    if(n%5==0 && n>=0) {
      printf("%d", n/5+2);
      return 0;
    }
    n -=3;
    if(n%5==0 && n>=0) {
      printf("%d", n/5+3);
      return 0;
    }
    n -=3;
    if(n%5==0 && n>=0) {
      printf("%d", n/5+4);
      return 0;
    }
    printf("-1");
    return 0;
}

 

이 코드를 while loop 을 적용해서 다시 작성하면 아래와 같이 작성할 수 있습니다.

#include <iostream>

int main() {
    int n, cnt=0;
    scanf("%d", &n);
    while (cnt<5) {
        if(n%5==0 && n>=0) {
            printf("%d", n/5+cnt);
            return 0;
        }
        n -=3;
        cnt++;
    }
    printf("-1");
    return 0;
}

 

이렇게 그리디 알고리즘에 대해서 알아봤습니다.

유용하셨다면, 공감과 구독 부탁 드립니다.

감사합니다. :)