[백준/JAVA] 2839 설탕 배달 - Dynamic Programming

문제

3kg, 5kg 봉지가 있을 때, 더 적은 수의 봉지를 챙길 수 있는 방법을 찾는 것

풀이

규칙을 찾아야 한다.

1부터 25쯤 까지 3kg 봉지와 5kg 봉지의 개수를 각각 적어서 나열보면
3kg 미만인 1kg, 2kg은 절대로 불가능한 경우이다.
4kg과 7kg또한 절대 불가능 경우다.

5의 배수의 경우 ( N % 5 == 0 일 경우 ) N/5 개 만큼의 봉지수를 챙긴다.
N % 5 == 1 의 경우 2 + ( a - 1 ) = a + 1
N % 5 == 2 의 경우 4 + ( a - 2 ) = a + 2
N % 5 == 3 의 경우 1 + a = a + 1
N % 5 == 4 의 경우 3 + ( a - 1 ) = a + 2

규칙성을 찾을 수 있다.

코드

코드 해석

절대 불가능한 경우 + N이 5의 배우의 경우 + 나머지가 1과 3의 경우 + 나머지가 2와 4의 경우를 나눠서 계산한다.

제출 코드

import java.io.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        int a = N / 5;
        int b = N % 5;

        int result = 0;

        if (N == 4 || N == 7) {
            result = -1;
        } else {
            if (b == 0) {
                result = a;
            } else if (b == 1 || b == 3) {
                result = a + 1;
            } else if (b == 2 || b == 4){
                result = a + 2;
            }
        }

        bw.write(String.valueOf(result));
        bw.flush();
    }
}