동적프로그래밍

gistfile1.cpp

#include <iostream>

const int MAX_NUM_BRIDGE = 10000;
const int MAX_NUM_VALUE  = 100;

typedef unsigned int index;

bool termscheck(int n)
{
  return n < MAX_NUM_BRIDGE ? true : false;
}

index min(int cost[], int a, int b, int c)
{

	if ( cost[a] <= cost[b] && cost[a] <= cost[c])	return a;
	if ( cost[b] <= cost[a] && cost[b] <= cost[c])	return b;
	if ( cost[c] <= cost[a] && cost[c] <= cost[b])	return c;

}

void main()
{
	int n = 0;

	std::cout<<"징검다리 수를 입력하세요 :";
	std::cin>>n;

	if (termscheck(n) == false)
	{
		std::cout<<"the value is out of range"<<std::endl;
		return;
	}

	if ( n == 2)
	{
		std::cout<<"최소 금액은 0원입니다."<<std::endl;
		return;
	}

	int* arr  = new int[n+1];
	int* cost = new int[n+1];
	int* l	  = new int[n+1];


	for (int i = 1 ; i < n+1 ; ++i)
	{
		std::cout<<i<<"번째 징검다리 값을 입력하세요 : ";
		std::cin>>arr[i];

		if ( i > 3)
		{
			l[i]	=	min(cost,i-1,i-2,i-3);
			cost[i]	=	cost[l[i]] + arr[i];
		}
		else
		{
			cost[i]	=	arr[i];
		}

	}



	int result = cost[min(cost,n,n-1,n-2)];
	std::cout<<"최소 금액은 : "<<result<<"입니다."<<std::endl;

	delete[] arr;
	delete[] cost;
	delete[] l;


}