[BOJ] 백준 1890번: 점프

https://www.acmicpc.net/problem/1890

1890번: 점프

프로그래밍 대회에서 배우는 알고리즘 문제해결전략(구종만 저, 이하 종만북) 책으로

동적 계획법(dynamic programming, 이하 dp)을 공부하다가 백준에서 비슷한 예제를 찾아 풀어보았습니다.

 

제가 dp 문제를 풀 때 풀이 방식은 다음과 같습니다. (https://blog.encrypted.gg/974 바킹독님 영향을 받았습니다.)

1) 문제를 풀기 위한 table을 정의

2) 점화식 찾기

3) 초기값 설정

 

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

int N, board[101][101], jumpDist;
ll dp[101][101];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			cin >> board[i][j];
		}
	}
	
	// dp[i][j] : (i,j)까지 이동할 수 있는 경우의 수
	// dp[i+jumpDist][j] += dp[i][j];
	// dp[i][j+jumpDist] += dp[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];	
		}
	}
	
	cout << dp[N][N];
}

 

점화식을 찾을 수 있다면 구현은 매우 쉽고, 속도가 빠르다는 장점이 있지만

어려운 dp 문제에서는 table을 정의하고 올바른 점화식을 찾기, table 채우는 순서 정하기가 쉽지 않습니다.

그러한 문제들에 대비하고 dp에 대한 이해를 높이고자 종만북으로 공부하게 되었습니다. 

 

초반부 재귀함수와 메모이제이션(memoization)을 이용한 top-down 방식으로 일관되게 dp 문제를 풀이하고 있습니다.

top-down 방식의 dp는 cache 배열을 채우는 순서가 헷갈릴 때 이를 고려하지 않아도 되기 때문에

편하다는 장점이 있습니다. 시간이 bottom-up에 비해 느리지만 그렇다고 시간초과가 발생하지는 않습니다.  

 

그러나 삼성SW 역량테스트와 같이 스택 메모리가 1MB로 매우 작게 제한되는 경우 함수 call의 깊이가 깊어지면

메모리 초과가 될 수 있어 되도록이면 bottom-up 방식으로 일관성있게 연습하는 것이 좋을 것 같습니다.

(그렇지 않은 경우 top-down으로 연습하셔도 무방합니다.)

 

cache 배열은 해당 (y,x) 지점으로부터 도착지점(N,N)까지 도달할 수 있는 경로의 수를 저장하고 있습니다.

solve(y, x)는 해당 (y,x) 지점으로부터 도착지점(N,N)까지 도달할 수 있는 경로의 수를 return하는 함수입니다.

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

int N, board[101][101];
ll cache[101][101];

ll solve(int y, int x){
	// 1. base condition
	if(y > N || x > N) return 0;
	if(y == N && x == N) return 1;
	
	// 2. reference
	ll& ref = cache[y][x];
	int jumpDist = board[y][x];
	if(!jumpDist) return 0;
	
	// 3. cache check
	if(ref != -1) return ref;
	
	// 4. solve
	return ref = solve(y + jumpDist, x) + solve(y, x + jumpDist);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			cin >> board[i][j];
		}
	}
	
	// init
	memset(cache, -1, sizeof(cache));
	
	cout << solve(1, 1);
}

 

구현은 어렵지 않았지만, 두 가지 놓친 점이 있었습니다.

1. top-down 방식의 풀이에서 solve 함수에서 jumpDist 변수를 전역변수로 설정했던 점

전역변수로 설정할 경우 잘못된 값을 저장, 출력하게 됩니다.

매 함수마다 고유한 지역변수로 jumpDist를 저장해야 우리가 원하는 로직으로 작동합니다.

 

2. jumpDist 변수의 값이 0이 될 수도 있다는 점

메모리초과의 원인이었습니다. 문제 조건을 꼼꼼하게 체크할 필요가 있습니다.

입력으로 0이 주어질 수 있기 때문에 계속 같은 함수를 call할 수 있어 메모리초과를 유발합니다.(stack overflow)

이를 막기 위한 조건을 추가해주어야 합니다. (도착하지 않았는데 jumpDist가 0이라면 도착 불가능하므로 0을 return)

bottom-up 방식에서는 jumpDist가 0일 때 continue로 계산을 건너뛰지 않을 경우 답이 다르게 나옵니다.

주어진 테스트 케이스의 경우 정답은 3인데 3+3=6, 6+6=12와 같은 불필요한 계산을 해 12를 출력하게 됩니다.

 

이외에도

경로의 개수는 2^63-1보다 작거나 같다.

문제 조건을 꼼꼼하게 체크하지 않는다면 long long 자료형을 사용하지 않고 int 자료형을 사용하여 답을 출력해 

오답을 낼 수도 있을 것 같습니다.