[백준 11060] 점프 점프

www.acmicpc.net/problem/11060

11060번: 점프 점프

 

 

이문제는 DP 개념을 이용해서 여러개의 경우의 수 중 도착에 가까운 순부터 

최적의 경우를 메모리에 저장하는 방식으로 문제를 풀었다.

 

// 점프 점프
#include <iostream>

#define MAX_N 1000 
using namespace std;

int g_nMap[MAX_N];
int g_nDP[MAX_N];

int Jump2End(int N, int nPos)
{
	if(g_nDP[nPos]!= 0)
	{
		return g_nDP[nPos];
	}
	else
	{
		if((nPos + 1) == N)
		{
			return 0;
		}
		else
		{
			if(g_nMap[nPos] == 0)
			{
				g_nDP[nPos] = -1;
				return -1;
			}
			else
			{
				int nMin = MAX_N + 1;
				int nTmp = 0;

				for(int i = 1; i <= g_nMap[nPos]; i++)
				{
					if((i+nPos) >= N)
						break;

					nTmp = Jump2End(N, (nPos + i)) + 1;

					if(nTmp == 0)
						continue;
					else if(nTmp < nMin)
						nMin = nTmp;
				}
				if(nMin == MAX_N + 1)
					nMin = -1;

				g_nDP[nPos] = nMin;

				return nMin;	
			}
		}
	}
}

int main(void)
{
	int N = 0;

	cin >> N;

	for(int i = 0; i < N; i++)
	{
		cin >> g_nMap[i];
	}

	cout << Jump2End(N, 0) << endl;

	return 0;
}