[백준] 2839번 - 설탕 배달

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

2839번: 설탕 배달

동적계획법 연습문제로 풀어보았다. 

 

이것이 코딩테스트다 5번 문제와 유형이 비슷하여 거의 그대로 풀었다! 다만 3,5로 주어진 자료가 있어서 더 쉽게 풀 수 있었던 것 같다.

 

배열을 초기화 시킬 때 3000으로 초기화 시켰다. 범위가 5000까지여서 가장 많이 넣더라도 3000을 초과시키지 않기 때문이다.

 

초기화 시킨 후에는 3 , 5 인 경우에 3000인 경우를 피해서 각각 구하였다. 15, 30, 45 와 같이 동시에 만나는 경우는 min 함수를 이용하여 작은 값으로 구하게 하였다.( 사실상 5가 가장 작을 것이다! )

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int N;
	cin >> N;

	vector<int> arr(5001, 3000);

	arr[3] = 1;
	arr[5] = 1;
	
	int drr[] = { 3,5 };

	for (int i = 0; i < 2; i++)
	{
		for (int j = drr[i]; j <= N; j++)
		{
			if (arr[j - drr[i]] != 3000)
			{
				arr[j] = min(arr[j], arr[j - drr[i]] + 1);
			}
		}
	}

	if (arr[N] == 3000)
	{
		cout << -1;
	}
	else
	{
		cout << arr[N];
	}
}