백준 1890. 점프

🅰 백준 1890. 점프

1890번: 점프

✏️ 문제 풀이

• dp에 현재 경로값을 저장해서 나감 배열 전체를 탐색하는 것이 아니라서 시간이 오래 안걸림
• 이중for문을 통해 배열을 반복하면서 이동할 수 있는지 확인 한 후, 이동 가능하면 check배열에 갈수있는 경로에 현재 check의 개수를 더해준다
• 배열을 확인 다 하면 마지막 지점이 정답이 된다.

✏️ 소스코드

package dp;

import java.io.*;
import java.util.*;

public class Main_실버2_1890_점프 {
	static int[][] map;
	static long check[][];

	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];
		check = 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());
			}
		}

		check[0][0] = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++){
				if (j + map[i][j] < N && map[i][j]!=0) 
                // 만약 이동한 값이 배열의 범위를 벗어나지 않고, 시작점이 종점이 아니라면
					check[i][j + map[i][j]] += check[i][j];	// 오른쪽으로 이동
				if (i + map[i][j] < N && map[i][j]!=0) 
                // 만약 이동한 값이 배열의 범위를 벗어나지 않고, 시작점이 종점이 아니라면
					check[i + map[i][j]][j] += check[i][j];	// 아래로 이동
			}
		}
		
		System.out.println(check[N-1][N-1]);
	}
}

 

✅ 후기

•