[Java] 백준 1890번 점프

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

1890번: 점프

풀이

---

(나의 생각)

1. 칸의 개수 입력받기

2. for 문으로 배열의 값 입력받기

3. 시작점은 배열의 첫번째 값으로 잡아두고 시작

4. 오른쪽, 아래의 경우를 비교할 필요없이 모두 따져야함(모든 경우의 수를 구해야되기 때문)

5. 경우의 수의 경우 int 값으로 저장해서 총 개수를 구한다? 

 

5번의 경우 int값으로 모든 경우의 수를 저장할 필요없이 dp배열에 값을 저장해 마지막 값을 출력하면된다.

 

---

각 칸의 기준으로 갈 수 있는 거리를 통해 갈 수 있는 경로의 개수를 업데이트!

int dist = map[i][j];
int down = dist + i;
int right = dist + j;
	 
if (down < n) { //칸수보다는 작아야 칸 안에서 돌 수 있기 때문에
	dp[down][j] += dp[i][j];
}
	 
if (right < n) {
	dp[i][right] += dp[i][j];
}

 

예외로 걸러도 되는 부분

① dp[i][j] = 0 인 경우

② 마지막 도착지점인 경우

dp[i][j] == 0 || (i == n - 1 && j == n - 1

 

코드

---

public class algo_1890_dp {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[][] map = new int[101][101];
	    long[][] dp = new long[101][101]; //경로의 개수는 263-1보다 작거나 같다. => long 사용
	    int n = sc.nextInt();
	 
	    dp[0][0] = 1; //기본값 설정
	 
	    for (int i = 0; i < n; i++) {
	        for (int j = 0; j < n; j++) {
	            map[i][j] = sc.nextInt();
	        }
	    }
	 
	    for (int i = 0; i < n; i++) {
	        for (int j = 0; j < n; j++) {
	        	//거르는 경우 : dp[i][j] == 0 , 마지막 도착지점인 경우
	            if (dp[i][j] == 0 || (i == n - 1 && j == n - 1)) {
	                continue;
	            }
	 
	            int dist = map[i][j];
	            int down = dist + i;
	            int right = dist + j;
	 
	            if (down < n) { //칸수보다는 작아야 칸 안에서 돌 수 있기 때문에
	                dp[down][j] += dp[i][j];
	            }
	 
	            if (right < n) {
	                dp[i][right] += dp[i][j];
	            }
	        }
	    }
	    //dp..출력..
	    System.out.println(dp[n - 1][n - 1]);
	}
}