[BAEKJOON]1890 점프

문제 요약

• 알고리즘 분류: 동적계획법, dp
• 난이도: Silver1
• 문제내용:
  • 가로세로 N개 길이의 게임판이 있다. 이동은 오른쪽 또는 아래만 가능하다.
  • (x, y)좌표에서 현재 칸에서 한번에 이동할수 있는 거리이다.
  • (1, 1)에서 (N, N)까지 갈수있는 경로수를 구해라

• 사이트:https://www.acmicpc.net/problem/1890

1890번: 점프

문제풀이

 이번 문제는 가로세로 최대 길이가 100이다. 제귀호출 방시으로 풀거나 브루드포스로 풀기에는 시간초과가 나오기 때문에 O(N)안에 푸는 방법을 찾아야 한다. 그래서 이번 문제 유형은  동적 계획법풀어야 된다. 동적계획법의 자세한 설명은 여기에 확인 해보면 된다. dp문제는 구현하는 능력보다 아이디어를 요구하기 때문에 점화식을 짜는 방법만 알면 쉽게 풀수 있다.

문제 접근 방법

  기존 DP에서는 현재 인덱스에서 이전에 값을 가져오는 방식이라면 이번에는 현재 인덱스에서 그 앞에 인덱스에 값을 추가하는 식으로 진행할것이다.

 

 위 그림처럼 (0, 0)에서 이동할수 있는 거리에 +1을 추가한것을 그림으로 표현한 것이다. 위 그림처럼 현재 위치 카운터에서 그 다음 이동할수 있는 위치에  카운터만 추가만 해주면 된다. 카운터를 추가하는 점화식은 아래와 같다.

• 오른쪽 이동: dp[i + board[i][j]][j] += dp[i][j]
• 아래로 이동: dp[i][j + board[i][j]] += dp[i][j]

그리고  이동거리가 0이면 자기 자신이동으로 카운터 + 하는것은 의미 없기 때문에  그냥 넘어가는시으로 진행하고 연산이 다 끝나면 (N, N) 카운터의 합을 출력하면된다. 

Code

Python

import sys
input = sys.stdin.readline

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
field = [[0] * N for _ in range(N)]
field[0][0] = 1
for i in range(N):
    for j in range(N):
        if board[i][j] == 0: continue
        if 0<= i + board[i][j] < N:
            field[i + board[i][j]][j] += field[i][j]
        if 0 < j + board[i][j] < N:
            field[i][j + board[i][j]] += field[i][j]

print(field[N - 1][N - 1])

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] board = new int[N][N];
		long[][] field = new long[N][N];
		StringTokenizer st;
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		field[0][0] = 1;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(board[i][j] == 0) continue;
				if( 0 <= i + board[i][j] && i + board[i][j] < N) {
					field[i + board[i][j]][j] += field[i][j];
				}
				if( 0 <= j + board[i][j] && j + board[i][j] < N) {
					field[i][j + board[i][j]] += field[i][j];
				}
				
			}
		}
		
		System.out.println(field[N- 1][N - 1]);		
	}

}