[백준] 2839. 설탕 배달(Java)

2839번: 설탕 배달

2839번: 설탕 배달

---

문제를 다시 정리해보면 다음과 같다.

• 사탕가게에 설탕을 정확히 N kg을 배달한다.
  • N은 3이상 5,000이하의 자연수
• 봉지는 3kg, 5kg 두 가지가 있고, 최대한 적은 봉지로 가져가려고 한다.
• 몇 봉지를 가져가야할까?

이에 대한 아이디어는 두 가지를 떠올릴 수 있었다.

첫번째는 그리디 방식으로 푸는 것이다.

3보다 5로 나누었을 때, 봉지 개수를 줄일 수 있기 때문에, N이 5로 나누어질 때까지, 3을 계속 빼자

1. 그리디 방식

두번째는 DP를 생각했다. dp[i]는 ikg까지 필요한 최소 봉지의 개수다.

• 모든 dp 배열을 최댓값 5001로 저장
• dp[3], dp[5] = 1로 설정
• 6부터 N까지
  • dp[i] = min(dp[i-3], dp[i-5]) + 1

2. DP 방식

전체 코드는 다음과 같다.

 

1. 그리디 접근법

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());
    int answer = 0;
    while(N>=0) {
      if(N%5 == 0) {
        answer += N / 5;
        System.out.println(answer);
        return;
      }
      N -= 3;
      answer++;
    }
    System.out.println(-1);
  }
}

2. DP 접근법

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());
    int[] dp = new int[5001];

    for(int i=0; i<N+1; i++) dp[i] = 5001; // dp배열을 모두 최댓값으로
    dp[3] = dp[5] = 1;
    for(int i=6; i<N+1; i++) {
      dp[i] = Math.min(dp[i-3], dp[i-5]) + 1;
    }
    System.out.println((dp[N]<5001)?dp[N]:-1);
  }
}