[BOJ 2839] 설탕배달

문제 출처

https://www.acmicpc.net/problem/2839

목적 : N kg 배달

제한사항 : 설탕 = 3kg, 5kg으로 구분

   설탕 N의 범위 (3<=N<=5000)

요구사항 : 최대한 적은 봉지를 출력

Ex) 18kg인 경우 5kg 3개 3kg 1개 총 4봉지만 배달하면 된다.

idea1 - Greed Algorithm을 이용

  => 항상 최적은 아님

  => 예외상황 존재

idea2 - N을 5로 나눈 몫을 5kg의 갯수 나머지를 3kg으로 나눈 몫을 3kg의 갯수로 정한다. 

    나머지가 생길경우 -1 return

  => 예외 상황 존재(input이 11인경우 output이 3이 나와야 하나 -1 나옴)

idea3 - 어쨋든 N은 3과 5로만 이루어져야하는 수!!!

  => 5가 최대가 되어야 봉지수가 최대한 적게 나온다!!

  => 이후 3으로 나눈 나머지가 0이면 답!

idea2에서 개선한 idea3 방법이 정답이였다. 이때 출력초과를 얻은 결과가 있는데 이와 같은 경우 값을 찾았음에도 불구하고 반복문을 돌기 때문에 모든 결과값을 출력하는 것을 알 수 있다 따라서 가장 먼저 값을 찾으면 루프를 빠져나올 수 있도록 개선하였다. 많은 실패가 따른 문제다..ㅠㅠ 아직도 실력부족...

#include <iostream> #include <stdlib.h> #define BIG_BAG 5 #define SMALL_BAG 3 using namespace std; int sol(int& n) { int quotient = n/BIG_BAG; while(quotient>=0) { int tmp = n - (BIG_BAG*quotient); if(tmp % SMALL_BAG == 0) return quotient + (tmp/SMALL_BAG); quotient--; } return -1; } int main(void) { int n; //input value(sugar's kg) cin>>n; if(n<3 || n>5000) exit(-1); cout<<sol(n)<<endl; return 0; }