[동적계획법, 난이도 중상] 백준 2839번 설탕배달

용량이 각각 3,5인 봉지가 있을 때, 얼마나 적은 봉지로 설탕을 모두 담을 수 있는가에 대해 물어보는 문제이다.

 

현재 설탕의 양이 i라고 했을 때, i-3만큼 이미 배분되어 있는 봉지수가 x이면 3만큼의 설탕을 용량이 3인 봉지 하나에 담아서 x+1만큼의 봉지수를 만들 수도 있고,

i-5만큼 이미 배분되어 있는 봉지수가 y이면 5만큼의 설탕을 용량이 5인 봉지 하나에 담아서 y+1만큼의 봉지수를 만들 수도 있다.

 

이 문제에선 최소 봉지 수를 이용해야 하므로 위 2가지 경우중 최솟값을 DP[i]값에 넣어주면 된다.

 

그런데 설탕양이 i-3 혹은 i-5 일 때 배분을 못한 상황이었다면 얘기는 달라진다.

둘다 배분을 못했다면 설탕양 i에 대해서는 아예 배분을 못할 것이고,

i-3만큼만 배분을 할 수 있다면 i-5일 때 최소로 배분한 봉지 수에 1을 추가해주면 되고,

i-5만큼만 배분을 할 수 있다면 i-3일 때 최소로 배분한 봉지 수에 1을 추가해주면 된다.

 

이러한 처리로 N=18까지 계산해준 표이다.

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int d[5001];
int maxi(int a,int b){
	if(a>b) return a;
	else return b;
}
int mini(int a,int b){
	if(a<b) return a;
	else return b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	d[1]=-1;
	d[2]=-1;
	d[3]=1;
	d[4]=-1;
	for(int i=5;i<n+1;i++){
		if(d[i-3]==-1&&d[i-5]==-1)d[i]=-1;
		else if(d[i-3]==-1) d[i]=d[i-5]+1;
		else if(d[i-5]==-1) d[i]=d[i-3]+1;
		else d[i]=mini(d[i-3]+1,d[i-5]+1);
	}
	cout << d[n];
}