알고스팟 외발뛰기 JUMPGAME

 

google88718171ab2cd781.html

0.00MB

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

algospot.com :: JUMPGAME

 

 

<접근방법>

완탐은 시간땜에 안됨->왜?->그렇다면 왜 이렇게 시간이 오래 걸리나->중복부분 탐색

 

 

완전 탐색이 만드는 경로의 개수는 n에 대해 지수적으로 늘어난다. 따라서 n=100이면 제한시간을 초과한다.

 

(이진트리그림)

 

 

그럼 어떻게 풀어야할까?

잘생각해보면 어떤 지점까지의 여러 경로는 중복되는 부분 문제가 많다. 그래서 dp로 풀면된다.

(재귀안될거 같은데.. dp인가?)

 

그럼 dp로 풀어보자.

일단 종만이행님이 가르쳐주신 dp의 기본골격을 때려박은 다음 생각해보자.

cache 배열에 들어갈 수 있는 상태가 뭐가 있을까?

(미방문), 이미 방문-(갈 수 있음), (갈 수 없음) 이렇게 3가지가 있다.

cache는 -1로 초기화가 되어있으니까 미방문은 -1, 갈 수 있음은 1, 갈 수 없음은 0으로 하겠다.

if 와 return 값을 잘 설정해주자.

이 때 마지막 return 값인 res = (jump(y + sz, x) || jump(y, x + sz)) 이게 잘이해가 안갔다.

 

jump(y, x) 는 (y, x)에서 마지막 점까지 도달할 수 있는가의 여부를 반환한다.

 

이렇게 생각하면 이해가 간다.

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

int tc, n, map[100][100], cache[100][100];

int jump(int y, int x) {
	//기저사례
	//-범위 밖
	if (y >= n || x >= n) return 0;
	//-목표 좌표 도달
	if (y == n - 1 && x == n - 1) return 1;

	int &res = cache[y][x];
	//중복부분
	if (res != -1) return res;

	int jump_sz = map[y][x];
	return res = (jump(y + jump_sz, x) || jump(y, x + jump_sz));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> map[i][j];
			}
		}
		memset(cache, -1 ,sizeof(cache));
		int res = jump(0, 0);

		if (res == 1) {
			cout << "YES" << '\n';
		}
		else {
			cout << "NO" << '\n';
		}
	}
	return 0;
}

 

 

 

 

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략