알고스팟_ 외발 뛰기 _ 동적 계획법

https://algospot.com/judge/problem/read/JUMPGAME

algospot.com :: JUMPGAME

풀이방법

이 문제는 시간 : 3초, 테스트케이스 : 최대 50개, n : 최대 100 의 조건이 주어졌다.

이 문제로 위와 밑으로 움직여 나올수있는 경로를 모두 구하기엔 시간이 너무 부족하다.

그래서 메모제이션을 적용하여 문제를 풀도록 하자.

 

먼저 재귀호출에서 시작하자. 재귀호출로 간단하게 밑과 같은 함수를 짤수 있을것이다.

bool jump(int y, int x)
{
	//범위를 넘어서면
	if (inRange(y, x) == false)
		return false;
	//도착하면
	if (y == n - 1 && x == n - 1)
		return true;

	int jumpSize = board[y][x];
	return jump(y + jumpSize, x) || jump(y, x + jumpSize);
}

 

이후, 메모제이션할 배열 cache를 만들어 위의 재귀함수를 보완한다. (자세한 내용은 주석에 넣어놨다.)

int cache[102][102];
//cache를 먼저 다 -1로 초기화
void cacheInit()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cache[i][j] = -1;
}
//return을 int형으로 바꾼 이유는 
//-1: 계산되지 않은상태, 0 : 갈수 없을때, 1 : 갈수 있을때  
//이렇게 3가지 경우의 수가 있기 때문이다.
int jump(int y, int x)
{
	//범위를 넘어서면
	if (inRange(y, x) == false)
		return 0;
	//도착하면
	if (y == n - 1 && x == n - 1)
		return 1;

	int &ret = cache[y][x];
	if (ret != -1) return ret;
	int jumpSize = board[y][x];
	return ret = (jump(y+ jumpSize, x) || jump(y, x + jumpSize));
}

---

전체코드

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

using namespace std;

int board[102][102];
int cache[102][102];
int n;

void cacheInit()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cache[i][j] = -1;
}

void Input()
{
	cin >> n;
	int value;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> value;
			board[i][j] = value;
		}
	}
	cacheInit();
}

bool inRange(int y, int x)
{
	if (y >= 0 && x >= 0 && y < n && x < n)
		return true;
	return false;
}

// -> , 
// |
// v
int dy[] = { 0, 1 };
int dx[] = { 1, 0 };

int jump(int y, int x)
{
	//범위를 넘어서면
	if (inRange(y, x) == false)
		return 0;
	//도착하면
	if (y == n - 1 && x == n - 1)
		return 1;

	int &ret = cache[y][x];
	if (ret != -1) return ret;
	int jumpSize = board[y][x];
	return ret = (jump(y+ jumpSize, x) || jump(y, x + jumpSize));
}

void solve()
{
	int ans = jump(0, 0);
	if (ans == 1)
		cout << "YES";
	else
		cout << "NO";
	cout << endl;
}

int main()
{
	int c;
	cin >> c;
	for (int i = 0; i < c; i++)
	{
		Input();
		solve();
	}
	return 0;
}

---

후기

종만북 최고