[백준] 2839번 설탕 배달

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q2839.java

N을 준다. 3kg과 5kg의 설탕 봉지를 이용해서 N을 만들 때 최소의 개수를 사용하는 경우를 구하여라.
N을 만들 수 없을 경우 -1을 출력한다.

처음 생각

이전에 풀어본것 같아서 검색을 해보니 풀어본 적이 있긴했었다. 보지는 않고 푼 후 비교를 해보니 접근 방식이 달리지긴 했다.([알고리즘/백준] - [문제] 백준 2839번(설탕 배달))

▶ 이전엔 그리디 적으로 수식으로 접근했었다.

다음 생각

이번에는 DP로 접근해서 풀이를 했다. N까지 접근을 하면서 3kg 짜리로 N에 접근할 수 있는 N-3에서의 값과 5kg 짜리로 N에 접근할 수 있는 N-5에서의 값 중 최소 개수이므로 작은 값을 택하면서 Bottom-up 방식으로 N까지 접근한다.

▶ 작은 값을 택해야하므로 배열의 초기화를 나올 수 없는 값인 9999로 해주었다.(최대 N이 5000이므로 9999는 나올 수 없다) 즉, 결과값인 dp[N]이 9999이거나 10000일 경우 불가능으로 -1을 출력해주었다.

▶ 10000을 제외 조건으로 포함시킨 이유는 둘 중 작은 값을 택한 후 +1을 해주어 설탕 묶음을 더해주었기 때문에 9999에서 +1한 값인 10000도 제외조건으로 해주었다.

방안

1) 수학적으로 접근해도 좋고 DP로 접근해도 좋고 다양한 방법이 더 있을 것 같다.

2) Java 풀이

package baekjoon.q1000;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class Q2839 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+10];
        Arrays.fill(dp,9999);
        dp[3] = 1;
        dp[5] = 1;
        // 3 짜리를 더해서 만들 수 있는 경우와
        // 5 짜리를 더해서 만들 수 있는 경우 중 작은 경우 선택
        for(int i=6;i<=n;i++)
            dp[i] = min(dp[i-3],dp[i-5])+1;
        if(dp[n]==10000 || dp[n]==9999) System.out.println(-1);
        else System.out.println(dp[n]);
    }
    private static int min(int x,int y){return x>y?y:x;}
}
 

3) C++ 풀이(Java 풀이를 토대로 짜보는 중인데 배우는 중이라 어색한 표현이 있을 수 있습니다!)

#include <iostream>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int dp[n+10];
    for(int i=0;i<n+10;i++)
        dp[i] = 9999;
    dp[3] = 1;
    dp[5] = 1;
 
    for(int i=6;i<=n;i++)
        dp[i] = min(dp[i-3],dp[i-5])+1;
    if(dp[n]==9999 || dp[n]==10000) cout << -1;
    else cout << dp[n];
    return 0;
}