백준 2839번: 설탕 배달 (Java, 동적 계획법)

☑️ 문제

https://www.acmicpc.net/problem/2839

✔️관련 알고리즘 개념

동적 계획법

☑️ 문제 분석

• 이문제는 Nkg으로 설탕의 무게가 주어졌을 때 3kg, 5kg 봉지를 최소 몇개로 만들 수 있느냐에 대한 문제이다.
• 봉지의 개수를 최소로 하려면 5kg이 최대한 많을 수록 좋다.
• 따라서 N이 5의 배수에 해당하는 값이라면 N/5의 값이 정답이 될 것이다.
• 하지만 5의 배수가 아닌 N의 값들이 문제인데
• 예시 입력 11은 3kg 2개, 5kg 1개, 18은 3kg 1개, 5kg 3개와 같이 3kg의 갯수도 고려해야 한다.
• 예시 입력 1: N=18
  • 18은 5의 배수아님 ⇒ 18 - 3 = 15 (count += 1)
    • N=18일 때는 5kg만으로 구성되지 않으므로 3kg으로도 채워준다.
    • 18 - 3 = 15, 3kg으로 옮긴 설탕을 제외한 값 15는 5의 배수이다.
    • 15 / 5 = 3이다. (count += 15/5)
    • 최종적으로 3kg 1개, 5kg 3개가 나오는 것이다.
• 예시 입력 5:N=11
  • 11은 5의 배수가 아님 ⇒ 11 - 3 = 8 (count += 1)
    • 11kg에서 일부를 3kg로 채웠는데 남은 값은 여전히 5의 배수가 아님
    • 8 - 3 = 5 (count += 1)
    • 남은 값 5는 5의 배수이므로 5kg 봉지로 채워준다.
    • 5/5 = 1 (count += 5/5)

⇒ 위의 과정을 재귀함수 형태로 구현한다.

☑️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(minNum(N, 0));
    }

    public static int minNum(int N, int count) {
        if (N < 0) return -1;              // 음수면 불가능
        if (N % 5 == 0) return count + N / 5;  // 5로 나눠지면 봉지 수 계산
        return minNum(N - 3, count + 1);   // 3을 빼고 계속 시도
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 재귀함수를 고려하여 알고리즘을 구성해내는게 어려웠다.