[ALGOSPOT] 알고스팟: 외발 뛰기

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

algospot.com :: JUMPGAME

[BOJ] 1890번: 점프 와 유사한 문제입니다.

 

#include <bits/stdc++.h>
using namespace std;

int C, N, board[101][101], jumpDist;
bool dp[101][101];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> C;
	
	while(C--){
		memset(dp, 0, sizeof(dp)); // 초기화 
		cin >> N;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				cin >> board[i][j];
			}
		}
		
		dp[1][1] = 1; // 초기값 설정 
		
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				jumpDist = board[i][j];
				if(!jumpDist) continue;
				if(i+jumpDist <= N) dp[i+jumpDist][j] |= dp[i][j];
				if(j+jumpDist <= N) dp[i][j+jumpDist] |= dp[i][j];	
			}
		}
		
		if(dp[N][N]) cout << "YES\n";
		else cout << "NO\n";
	}
}

 

dp[i][j] : i행 j열까지 도달할 수 있으면 1, 도달할 수 없으면 0의 값을 갖는다.

 

dp table을  위와 같이 정의하면 점화식은 위 코드와 같이 세울 수 있습니다.(bottom-up)

위 코드에서 반복문 내부의 if(!jumpDist) continue; 는 이 문제 조건에서는 없어도 무방합니다.

jumpDist 값이 0인 부분은 마지막 N행 N열뿐이기 때문에 아래의 OR 연산을 수행해도 같은 결과를 갖게 됩니다.

 

다만 문제 조건이 [BOJ] 1890: 점프 처럼 문제 조건에 마지막 N행 N열 이외에도 0 값이 들어갈 수 있다고 가정했을 시에  자기 자신과의 OR 연산을 수행하므로 같은 결과를 가져 문제 정답을 도출하는 데에는 문제가 없으나 

불필요한 연산을 두 번씩 수행하게 되므로 continue로 이를 막는 것이 좋겠습니다.

 

종만북에서 소개된 바와 같이 top-down 방식으로 코드를 작성하면 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int C, n, board[101][101];
int cache[101][101];

int solve(int y, int x){
	// base condition
	if(y > n || x > n) return 0;
	if(y == n && x == n) return 1;
	
	int &ref = cache[y][x];
	int jumpDist = board[y][x];
	
	if(ref != -1) return ref;
	return ref = (solve(y + jumpDist, x) ||	solve(y, x + jumpDist));
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> C;
	
	while(C--){
		cin >> n;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				cin >> board[i][j];
			}
		}
		memset(cache, -1, sizeof(cache));
		if(solve(1,1)) cout << "YES\n";
		else cout << "NO\n";
	}
}

 

주의할 점

 ALGOSPOT 문제나 삼성SW 역량테스트와 같이 여러 개의 test case가 주어지는 경우

꼭 dp 배열이나 cache 배열 등을 memset이나 반복문 등을 통해 초기화하는 습관을 들이는 것이 좋습니다.