[백준] BOJ 2839 설탕 배달

cat_dev·2021년 2월 18일
0

알고리즘

목록 보기
1/10
post-thumbnail

문제 링크

문제 해석

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

문제 풀이

무식하게 풀 수 있는가?

💡 완전 탐색으로 풀기! 설탕 봉지 개수를 기록하며 풀었다.

1️⃣ 어떤 것을 메모하면 좋을까?

문제에서 "최대한 적은 봉지" 수를 찾아야 한다고 했으므로
한번에 최대한 많은 용량의 봉지, 즉 5킬로짜리 봉지를 담아야 한다.
따라서 5킬로짜리 봉지 개수 메모를 배열로 만들고, 3킬로짜리 봉지 개수를 메모하기로 했다.

2️⃣ 메모 형태는 어떻게?

5킬로짜리 봉지의 개수를 배열의 index로!
배열의 값은 3킬로짜리 봉지의 값으로 설정했다.

5[0] = 3 //5킬로 봉지 0개, 3킬로 봉지 3개
5[1] = 2 //5킬로 봉지 1개, 3킬로 봉지 2개
5[2] = -1 //5킬로 봉지 2개를 써서 해당 설탕 무게를 맞출 수 없음

문제에서 5킬로와 3킬로짜리 봉지로 해당 설탕 크기를 나를 수 없다면 -1을 출력하라고 했기 때문에
배열의 초기값을 -1로 설정했다.

3️⃣ 적당한 메모장 크기 찾기

11킬로짜리 설탕을 나르는 데 5킬로 봉지는 최대 2개 필요하므로
입력 최대 크기인 5000/5 = 1000, 길이 1000의 배열을 만들 필요가 없다.
따라서 입력받은 수를 5로 나눈 몫보다 하나 큰 크기의 배열을 생성해 -1로 초기화하도록 했다.

4️⃣ 설탕 봉지 개수 구하기

  1. 우선 5킬로 봉지를 입력값에서 뺀다.
  2. 남은 입력값을 3으로 나눠 나머지가 0이면 몫을 메모
  3. 나머지가 0이 아닐 경우 continue

문제 풀이 코드

package DP;

import java.util.Scanner;

import static java.lang.Math.min;

public class BOJ2839 {
    static int sugar;
    static int memo[];

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        sugar = s.nextInt();
        //배열 크기 정하기
        int length = sugar / 5;

        //메모 배열 초기화
        memo = new int[length+1];
        for (int i = 0; i <= length; i++) {
            memo[i] = -1;
        }

        //메모하기
        for (int i = 0; i <= length; i++) {
            int temp = sugar - (5 * i);
            if (temp % 3 == 0) {
                memo[i] = temp / 3;
            }
        }

        //배열 최소값 찾기
        int min = 1001;
        int index = 0;
        for (int i = 0; i <= length; i++) {
            if (memo[i] != -1) {
                int lastmin = min;
                min = min(min, memo[i]);
                if (lastmin != min) {
                    index = i;
                }
            }
        }
        //최소 값 출력
        if (min == 1001) {
            System.out.println(-1);
        }
        else{
            System.out.println(min + index);
        }

    }
}
profile
devlog

0개의 댓글