18/03/13 · Log.dev() Algorithm BOJ

BOJ 2839 설탕배달

설탕배달

n kg의 설탕을 5kg짜리, 3kg짜리 봉지에 딱 떨어지게 담을 때 최소한의 봉지갯수 구하기

  1. 모두 5kg짜리 봉지에 담아본다
  2. 설탕이 남으면 3kg짜리에 담아본다
  3. 그러고도 남으면 5kg짜리를 하나 푼다
  4. 2~3을 반복해서 딱 떨어지면 5kg짜리, 3kg짜리 봉지의 수를 구한다.
  5. 딱 떨어지지 않으면 배달 안함

    의 순서로 풀었다.
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        
        int five = input/5;
        int three = 0;
        input = input%5;
        
        while(five>=0){
            if (input%3==0){
                three = input/3;
                input %= 3;
                break;
            }
            five--;
            input+=5;
        }
        
        System.out.println(five<0?-1:five+three);
    }
}

다른 풀이법

내가 푼 방법 말고 다른 방법을 찾아봤는데 다이나믹프로그래밍으로 풀어낸 방법이 있었다.
가서 보기

미리 입력 범위 안의 모든 답들을 구해 배열에 넣어놓고 마지막에 입력된 값의 답을 인덱스로 접근해 가져오는 방법인 것 같다.

다이나믹 프로그래밍이라고 하는데 좀 더 알아봐야겠다.

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket
Comments powered by Disqus