[JAVA] 백준 (실버4) 2839번 설탕 배달

링크

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

---

입력 예제

18

---

출력 예제

4

---

풀이

Nkg을 3kg와 5kg의 봉지로 나눌 때 봉지의 개수가 최소가 될 때를 구해야 한다.

dp 배열을 다음과 같이 정의한다.

dp[i]: i kg일 때 봉지의 최소 개수

우선 점화식을 찾기 위해 규칙성을 찾아본다.

• dp[3] = 1
• dp[4] = 0
• dp[5] = 1
• dp[6] = 2 -> dp[3] + 1 (3kg 추가)
• dp[7] = 0
• dp[8] = 2 -> dp[3] + 1 (5kg 추가)
• dp[9] = 3 -> dp[6] + 1 (3kg 추가)
• dp[10] = 2 -> dp[5] + 1 (5kg 추가)
  ...

결국 3kg 또는 5kg을 추가해가는 것이기 때문에 최소 개수가 되기 위해

1. 우선 5kg를 추가할 수 있는지 확인하고 (dp[i-5] != 0) 추가할 수 있다면 값을 갱신한다. (dp[i] = dp[i-5] + 1)
2. 그리고 5kg를 추가할 수 없고 3kg만 추가할 수 있다면 (dp[i-3] != 0) 값을 갱신한다. (dp[i] = dp[i-3] + 1)

가령 12kg의 봉지 개수를 구한다면 dp[9]와 dp[7]을 확인하고 dp[7]은 0이기 때문에 5kg는 추가할 수 없고, 3kg를 추가할 수 있으므로 dp[12] = dp[9] + 1이 된다.

for (int i = 6; i <= N; i++) {
    if (dp[i - 5] != 0) {  //5kg 봉지를 추가할 수 있을 때
        dp[i] = dp[i - 5] + 1;
    } else if (dp[i - 3] != 0) {  //3kg 봉지를 추가할 수 있을 때
        dp[i] = dp[i - 3] + 1;
    }
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        if (N == 3) {
            System.out.println(1);
            return;
        } else if (N == 4) {
            System.out.println(-1);
            return;
        }

        //dp[i]: i kg일 때 봉지의 최소 개수
        int[] dp = new int[N + 1];

        dp[3] = 1;
        dp[5] = 1;

        for (int i = 6; i <= N; i++) {
            if (dp[i - 5] != 0) {  //5kg 봉지를 추가할 수 있을 때
                dp[i] = dp[i - 5] + 1;
            } else if (dp[i - 3] != 0) {  //3kg 봉지를 추가할 수 있을 때
                dp[i] = dp[i - 3] + 1;
            }
        }

        if (dp[N] == 0) {
            System.out.println(-1);
        } else {
            System.out.println(dp[N]);
        }
    }
}