상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지
와 5킬로그램 봉지
가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N
킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
첫째 줄에 N
이 주어진다. (3 ≤ N ≤ 5000)
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N
킬로그램을 만들 수 없다면 -1
을 출력한다.
18
4
4
-1
6
2
9
3
1
3
Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 1번
-문제를 번역한 사람: baekjoon
-데이터를 추가한 사람: hyunynim, jh05013
import java.util.Scanner;
public class Code2839 {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int N=scanner.nextInt();
int count=0;
int temp=N;
int answer=0;
while(temp!=0){
if(temp/5>0){
count+=temp/5;
temp=temp%5;
}
if(temp/3>0){
count+=temp/3;
temp=temp%3;
}
if(temp<=2 && temp!=0){
count=-1;
break;
}
}
int firstcount=count;
count=0;
temp=N;
while(temp!=0){
if(temp%3==0){ //3의 배수
count=temp/3;
break;
}
if(temp%5==0){
count=temp/5;
break;
}
else{
count=-1;
break;
}
}
int secondcount=count;
count=0;
temp=N;
int min=-1;
if(N>=5){
while(temp!=0){ //여기가 문제.
min=-1;
for(int i=1;i<=N/5;i++){
temp=N;
if(temp>=5){
temp=temp-5*i;
count=count+i;
if(temp==0){
if(min==-1){
min=count;
}
else{
if(min>count){
min=count;
}
}
break;
}
}
if(temp%3==0){
count+=temp/3;
temp=temp%3;
}
else{
temp=temp%3;
}
if(temp<=2 && temp!=0){
count=-1;
}
if(min==-1){
min=count;
}
else if(count==-1){
count=0;
continue;
}
else{
if(min>count){
min=count;
}
}
min=count;
count=0;
}
temp=0;
}
}
int thirdcount=min;
if(secondcount==-1){
if(thirdcount==-1){
answer=firstcount;
}
else{
if(firstcount==-1){
answer=thirdcount;
}
else{
if(firstcount<thirdcount){
answer=firstcount;
}
else{
answer=thirdcount;
}
}
}
}
else if(firstcount==-1){
if(thirdcount==-1){
answer=secondcount;
}
else{
if(secondcount==-1){
answer=thirdcount;
}
else{
if(secondcount<thirdcount){
answer=secondcount;
}
else{
answer=thirdcount;
}
}
}
}
else if(thirdcount==-1){
if(firstcount==-1){
answer=secondcount;
}
else{
if(secondcount==-1){
answer=firstcount;
}
else{
if(secondcount<firstcount){
answer=secondcount;
}
else{
answer=firstcount;
}
}
}
}
else{//다 -1이 아니다..
if(firstcount<=secondcount){
if(firstcount>=thirdcount){
answer=thirdcount;
}
else{
answer=firstcount;
}
}
else{
if(secondcount>=thirdcount){
answer=thirdcount;
}
else{
answer=secondcount;
}
}
}
System.out.println(answer);
}
}
다 풀고 소스코드를 봤는데 저렇게 간단해질 수 있다니..
5로 안나눠지는 동안만 3을 빼고 그 횟수만큼 ++해주고,
그다음 0보다 작지않으면, 그 수를 또 5로 나눈 몫으로 하다니..
나는 3가지 경우의 수를 나눠서 생각했다.
먼저 5로 나눴을 때 나머지를 또 3으로 나누고,
5를 N번 빼고 3으로 나눴을 때
그리고 5로 나눠지고, 5로 안나눠지면 3으로 나눠질때
이제..종말의 수 666을 해결하러 가봐야겠다!