[Baekjoon Online Judge] 2839. 설탕 배달 (C++, Java)

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

 

설명

---

핵심

이 문제의 핵심은 5kg 봉지가 많을수록 더 적은 봉지로 채울 수 있다는 것이다.

단, 주어진 용량을 꽉 채워야 한다.

 

그리고 

N이 최대값인 5000일 때, 가장 무식한 방법으로 푼다고 생각해보자.

1. 먼저 5kg 봉지만으로 채워본다.

2. 그 다음 3kg 봉지를 1개 넣고 나머지를 모두 5kg 봉지로 채워본다.

...

?. 3kg 봉지만으로 채워본다

딱 봐도 너무 무식해서 이렇게 풀고싶지는 않을 것이다.

위 방식의 문제는 최초에 5kg으로 채우는 과정에서 알아낸 데이터를 다 버리고 다음 단계에서 새로 시작한다는 것이다.

따라서 앞서 계산한 부분 문제의 해를 기억하여 반복을 줄이는 동적 프로그래밍을 사용하면 될 것 같다.

---

구현

두 서로 다른 언어와 구현 방식을 사용해 보았다.

Code (C++) 

5kg 봉지가 많을수록 좋다는 원칙을 기반으로 구현한 코드

#include <iostream>
using namespace std;

int foo(int);

int main() {
	int n;
	cin >> n;
	cout << foo(n) << endl;
	return 0;
}

int foo(int n) {
	int temp = -1;
	for (int i = 0; ( 5*i ) <= n ; i++) {
		if ( (n-(5*i))%3 == 0)
		temp = i + ((n-(5*i))/3);
	}
	return temp;
}

Code (Java)

DP를 이용한 코드

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));
        final int N = Integer.parseInt(br.readLine());
        int[] d = new int[N + 1];

        d[0] = 0;
        for (int i = 1; i <= N; i++) {
            d[i] = Integer.MAX_VALUE;
            if (i >= 3 && d[i - 3] != Integer.MAX_VALUE) {
                d[i] = Math.min(d[i], d[i - 3] + 1);
            }
            if (i >= 5 && d[i - 5] != Integer.MAX_VALUE) {
                d[i] = Math.min(d[i], d[i - 5] + 1);
            }
        }

        System.out.println(d[N] == Integer.MAX_VALUE ? -1 : d[N]);
    }
}