백준 2839 Java

문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 
설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 
3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

이 문제의 규칙을 찾아보자
규칙1 :  4와 7 을 제외한다면 어떠한 숫자든 3,5를 이용해 구성할 수 있다.

규칙2 : suger % 5 를 하였을때에 나머지 값이 1이라면 마지막 자리의 숫자는 6이라는것이고
suger % 5 를 하였을때에 나머지 값이 3이라면 마지막 자리의 숫자는 8이라는 것이다
6은 3kg 2봉지, 8은 5kg 1봉지 3kg 1봉지로 구성이 가능하다.
       
규칙3 :suger % 5 를 하였을때에 나머지 값이 2라면 십의자리 이상일때 숫자는 17이라는것이고
suger % 5 를 하였을때에 나머지 값이4라면 마지막 자리의 숫자는 9라는것이다.
17은 3kg 4봉지, 5kg 1봉지, 9는 3kg 3봉지로 구성이 가능하다.
   
1. (suger == 4 || suger == 7)
4와 7을 제외한다면 어떤 숫자든 3, 5를 이용해 구성이 가능함으로
정확하게 N키로 그램을 만들 수 없는 4, 7은 -1을 출력하여준다.

2. (suger % 5 == 0)
suger % 5 를 하여 나머지값 0이 나온다면
5kg의 봉지로 전부 구성할 수 있다는것이기 때문에
suger / 5 = ? 를 이용하여 답을 구해준다

3. (suger % 5 == 1 || suger % 5 == 3)
(suger % 5 == 1) 5로 나머지값을 구했을때에 1이 나온다는것은
마지막 자리에 6이라는 숫자가 들어갔을때 뿐인데 6이라면 3kg 2봉지로 구성이된다
이때에 16이 들어갔다치면 5kg 2봉지, 3kg 2봉지로 구성할 수 있는데
(16 / 5) + 1 = 4 라는 최소 봉지 개수가 나오게되며,
(suger % 5 == 3) 5로 나머지값을 구했을때에 3이 나온다는것은
3kg 한봉지만 더 더해주면 최소 봉지개수를 구할 수 있다는 것이다.

4. (suger % 5 == 2 || suger % 5 == 4)
(suer % 5 == 2) 5로 나머지값을 구했을때에 2가 나온다는것은
마지막 자리에 7이라는 숫자가 들어갔을때이다 이때에 일의자리만 있는 7은 미리
제외하였음으로 십의자리 이상의 마지막자리에 7이 들어갔을때 뿐인데
17이라는 숫자가 들어갔다고 가정한다면 5kg 1봉지, 3kg 4봉지로 구성할 수 있다
이때에 17 % 5를 한다면 3이라는 값이 나오고 + 2를해주면 5봉지라는 값을 구할 수 있다.
(suger % 5 == 4) 5로 나머지값을 구했을때에 4가 나온다는것은
마지막 자리에 9라는 숫자가 들어갔을때이며 9가 나왔다고 할때에
suger / 5 = 1이라는 숫자가 나오고 +2를 해준다면 3봉지 즉,
9kg은 3kg 3봉지로 구성할 수 있는데
(suger / 5) + 2를 해준다면 최소 봉지개수를 구할 수 있다.

 

뭔가 쉽게 답이 나오는거같은데 이 문제는 규칙을 차고 경우에 수를

몇번 구하니 나왔다... 암산 노가다라고 해야할까나

물론 이 경우에 수를 구하기까지 꽤나 많이 생각하였지만... ㅎㅎ