백준 2839번 설탕배달 (Java)

 

막상 보면 매우 쉬운 문제 같지만, 알고리즘을 짜려고 들어가면 생각보다 어렵다. 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int sugar=scanner.nextInt();
        int count=0;

        if(sugar%5>3){
            count=sugar/5;
            sugar=sugar-5*count;
        }
        else if(sugar%5<3){
            System.out.println(-1);
        }
    }
}

내가 처음에 짜고있던 코드다. 봉지수를 최소화 하려면 5kg짜리 봉지를 최대한 많이 사용해야 한다. 따라서 처음에는 5kg짜리로 나눠서 봉투수를 구한다음에 3kg짜리로 다시 나누려고 했지만, 만약 9kg짜리 설탕을 나눌땐, 5kg으로 나눈 후 4kg이 남아버려서 3kg으로도 완벽히 나누지 못해 나눌수 없게 된다. 처음부터 3kg짜리로 나누게 되면 최소 봉투수가 아니라 최대 봉투수가 되어버리므로 이 방법은 틀렸다. 

 

문제 단계가 기본 수학이니, 규칙성을 찾아보기로 했다. 이런 류의 문제는 대부분 규칙성을 가지고 있거나 특정한 수열을 가지고 있다. 알고리즘 구현능력을 테스트하는게 아닌 수학능력을 테스트하려는 문제같다. 그리고 여러가지 풀이 방법을 참고하였다.

 

참고:gabii.tistory.com/entry/BaekJoonC-백준-2839번-설탕배달

[BaekJoon/C] 백준 2839번 설탕배달

medium.com/wasd/백준-c-알고리즘-풀이-2839번-372de7d86de6

[백준] C 알고리즘 풀이 — 2839번

st-lab.tistory.com/72

[백준] 2839번 : 설탕 배달 - JAVA [자바]

 

풀이 방법은 크게 2가지로 나뉘었다. 수학적으로 접근해서 풀이, 반복문으로 하나씩하나씩 빼고 확인하는것이다. 반복문으로 풀때는 한번에 개수를 구하는 것이 아닌, 5kg으로 뺄수 있는지 없는지, 3kg으로 뺄수 있는지 없는지, 더이상 뺄 수 있는지 없는지를 조건으로 건 후 이를 계속 반복하는 것이다. 구현하기 쉽지만, 수가 커지면 실행시간역시 그에 비례해서 늘어난다는것이 단점이다.

이를 의사코드로 표현하면\

while(true){
	if(sugar%5==0){
        sugarbag=sugarbag+sugarbag/5;
        break;
    }
    else if(sugar<0){
    	print(-1);
        break;
    }
	sugar=sugar-3;
    sugarbag++;
}

같이 된다.

 

수학적으로 푸는 방법은 

5의 배수를 기준으로 5의 배수+1,+3이 설탕을 5로 나눈 몫의 +1이 봉투의 수가 되는 규칙성이 있으므로 이를 이용해서 풀면 된다. 자세한 풀이는 참조링크에 자바로 풀이한 곳으로 들어가면 된다.

 

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int sugar = in.nextInt();
        if (sugar == 4 || sugar == 7) {
            System.out.println(-1);
        }
        else if (sugar % 5 == 0) {
            System.out.println(sugar / 5);
        }
        else if (sugar % 5 == 1 || sugar % 5 == 3) {
            System.out.println((sugar / 5) + 1);
        }
        else if (sugar % 5 == 2 || sugar % 5 == 4) {
            System.out.println((sugar / 5) + 2);
        }
    }
}