[알고스팟] JUMPGAME - 외발 뛰기 (C++)

문제

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

algospot.com :: JUMPGAME

 

풀이

간단한 다이나믹 프로그래밍 문제

 

해당 위치에서 끝에 도달이 가능한지의 여부를 is_pos_board에 저장해두어 중복된 호출을 방지하여 최적화한다.

해당 위치의 도달 여부가 기록되어있다면 바로 그 값을 반환하고 아니라면

왼쪽과 오른쪽으로 이동하는 경우를 재귀호출하여 반환된 값을 기록한다.

 

코드

	#include <iostream>
	#include<string.h>
	using namespace std;
	int board[100][100];
	int board_size;
	int is_pos_board[100][100];
	bool checkBoard(int r,int c){
	if(r>= board_size || c>=board_size)
	return false;
	if(is_pos_board[r][c] != -1)
	return is_pos_board[r][c];
	if(r== board_size -1 && c == board_size-1)
	return true;
	int& ret = is_pos_board[r][c];
	ret = checkBoard(r+board[r][c], c) || checkBoard(r, c+board[r][c]);
	return ret;
	}
	int main() {
	int test_num;
	cin>>test_num;
	for(int i=0; i<test_num ; ++i){
	cin>>board_size;
	for(int j=0; j<board_size ; ++j)
	for(int k=0; k<board_size ; ++k)
	cin>>board[j][k];
	memset(is_pos_board, -1, sizeof(is_pos_board));
	if(checkBoard(0, 0))
	cout<<"YES\n";
	else
	cout<<"NO\n";
	}
	return 0;
	}

view raw [AlgoSpot]_JUMPGAEM_외발 뛰기.cpp hosted with ❤ by GitHub