[Java] 백준 1890번 점프

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

1890번: 점프

문제 설명

• N : 게임 판의 크기
• 게임판에 쓰인 수만큼 오른쪽 혹은 아래쪽으로만 점프 가능
• 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 이동할 수 있는 경로의 개수 구하기
• 단, 가장 오른쪽 아래 칸 수는 0 (종착점)

오른쪽으로 이동했을 때와 아래칸으로 이동했을 때 두 가지 경우로 나누어 생각하면 쉽게 규칙을 찾을 수 있다.

graph [][] : 게임판 , dp [][] : 경로의 수라고 하자.

graph [][]에는 점프할 수 있는 수가 적혀있다.

따라서,

 

1. 오른 칸으로 점프했을 때

 right = j + graph [i][j] 

만약 오른쪽으로 점프했을 때의 칸이 게임판의 크기보다 작다면

 if(right <=N) dp [i][right]+=dp [i][j] 

 

2. 아래 칸으로 점프했을 때

 down = i + graph [i][j] 

만약 아래쪽으로 점프했을 때의 칸이 게임판의 크기보다 작다면

 if(down <=N) dp [down][j]+=dp [i][j] 

 

주의할 점!

1. 경로의 개수가 2^63 -1개이기 때문에  dp 배열의 자료형은 long 형태 이어야 한다.

2. dp [1][1]의 시작점은 1로 초기화해준다 -> 초기화하지 않으면 계속 0으로 계산됨.

3. 종착점에 대한 조건을 주어야 종착점에서의 경로수가 계산되지 않는다.

import java.util.Scanner;

public class Main {
	public static void main(String [] args) {
		Scanner s= new Scanner(System.in);
		
		int N = s. nextInt(); //게임판의 크기
		int graph[][] = new int[N+1][N+1]; //게임판
		long dp[][] = new long[N+1][N+1]; //경로의 수
		
		
		for(int i=1;i<=N;i++) 
			for(int j=1;j<=N;j++) 
				graph[i][j]=s.nextInt();
		
		dp[1][1]=1; //시작점 초기화
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				if ((i == N && j == N) && graph[i][j]==0) break; //종착점에선 계산하지 않는다.
				else {        
				int right = j + graph[i][j]; 
				int down = i + graph[i][j];
				
				if(right<=N) dp[i][right]+=dp[i][j];
				if(down<=N) dp[down][j]+=dp[i][j];
				}
			}
		}
		
			System.out.println(dp[N][N]);
	}
}