BOJ 1890 점프

www.acmicpc.net/problem/1890

1890번: 점프

 

 

문제 분석

- dp문제이다. 

- 오른쪽으로 가야할 경우와 아래로 가야할 경우를 잘 고려하여 메모이제이션을 수행한다.

 

 

문제 풀이

1) 게임판의 값을 입력받는다.

2) dp의 시작좌표는 1로 초기화한다 (1에서 더해나가야하기때문이다. 0인 경우 계속 0으로 처리되어 경로의 개수가 증가되지 않는다)

3) 2차원 배열의 좌표를 탐색한다.

4) 아래쪽으로 가야할 범위가 충족되었다면 아래쪽으로 이동 후 기존의 값을 더해준다.

5) 왼쪽으로 가야할 범위가 충족되었다면 왼쪽으로 이동 후 기존의 값을 더해준다.

6) 반복 수행 후 조건에 탐색을 종료하면 마지막 종착점의 경로 개수를 출력한다.

 

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

public class Main {

	private static int[][] map; // 게임판
	private static long[][] dp; // 경우의 수

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		dp = new long[N][N];

		for (int i = 0; i < N; i++) { // 입력
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 입력-end

		dp[0][0] = 1; // 시작좌표 초기화

		for (int i = 0; i < N; i++) { // 입력
			for (int j = 0; j < N; j++) {
				int jump = map[i][j];
				
				if (map[i][j] == 0 || dp[i][j] == 0) // 게임판의 값이 0(목적지 도달) or dp의 값이 0인 경우 더이상 이동하지 못하므로 고려하지 않는다.
					continue;
				
				if(i+jump <N) { // 가야할 범위 확인
					dp[i+jump][j] += dp[i][j];
				}
				
				if(j+jump<N) {
					dp[i][j+jump] += dp[i][j];
				}

			}
		}

		System.out.println(dp[N-1][N-1]);

	}// main

}// class-end