📝 문제

바로가기
설탕을 3kg, 5kg 용량의 봉지에 가득 담아서 배달할 때 최소의 봉지로 배달하는 경우를 계산하는 문제

📌 코드

/**
 * @Date : 2021-04-11
 * @Title : 설탕배달
 * @Desc : 설탕 N kg을 배달하는데 3kg과 5kg 봉지에 담아서 배달한다. 가장 적은 봉지로 배달할 때의 봉지 개수
 *         3과 5로 딱 나누어떨어지도록 담을 수 없는 경우 -1을 반환
 */

package Baekjoon;

import java.util.*;
import java.io.*;

public class BOJ2839 {

    static int n; //총 배달해야할 설탕의 무게
    static int answer = 0; //필요한 최소 봉지 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());

        /**
         * n을 5로 나누었을때
         * -> 1. mod == 0 : 몫이 답
         * -> 2. mod != 0 : n-3, cnt+1, 다시 검사
         */
        while (n > 0) {
            if(n % 5 == 0) {
                System.out.println((n/5) + answer);
                return;
            } else {
                n -= 3;
                answer++;
            }
        }
        if(n == 0) System.out.println(answer);
        /* n이 0보다 작아졌을 경우 : 봉지로 나눌 수 없는 경우 */
        else System.out.println(-1);
    }
}

💊 생각이 필요한 부분

• 계산의 각 단계에서 도출되는 답을 저장해둬야한다.
• 5로 나누어떨어질 경우 5로 나누는 것이 최적의 방법이고, 아닐 경우는 3을 뺀다는 개념으로 점화식을 작성한다.