BOJ - 1890 ) 점프

 

---

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

1890번: 점프

 

---

DP는 너무나도 어려운것 같다.

 

점프는 맵에 표시된 수만큼 오른쪽과 아래로 점프한다.

 

최종 목적지까지 가는 경로를 찾아주면된다.

 

중간에 한 지점을 생각해서 그 지점에 올수있는 경우의 수가 DP값에 저장된다.

 

처음 시작지점에 DP 값을 1로 설정하여 움직일수있는 지점에다가 현재의 DP값을 저장해준다.

 

그렇게 누적되어가는 값이 그 지점으로 올수있는 경우의 수를 뜻한다.

 

즉 그게 마지막 지점이면 처음에서 시작해서 마지막에 올수있는 모든 경우의 수이다.

 

처음에는 BFS로 QUEUE에 좌표를 넣고 진행하려했었지만 시간초과가 날것 같았다.

 

또한 문제에서 경우의수는 2^63-1이라고 지정해준것을 못봐서 70%에서 계속 틀렸다고 나왔다.

 

경우의수를 저장해주는 DP배열을 long형으로 바꾸어 주어야했다ㅠ

 

또한 디버깅하다가 맨 마지막 지점에 도착했을때 좌표가 0 0 이므로 자기 자신의 값을 한번더 더하는 예외가 발생하여 

 

처리해주었다. DP너무어렵다 ㅠㅠ

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N =Integer.parseInt(st.nextToken())+1;
        int map[][] = new int[N][N];
        long dp[][] = new long[N][N];
        dp[1][1] =1;
        for(int y = 1 ; y < N ; y++) {
            st = new StringTokenizer(br.readLine());
            for( int x = 1 ; x < N ; x++) {
                map[y][x] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int y = 1 ; y < N ; y++) {
            for(int x = 1 ; x < N ; x++) {
                if(dp[y][x]==0 || (x==N-1 && y == N-1)) continue;
                
                if(y+map[y][x] <N)dp[y+map[y][x]][x]+=dp[y][x];
                if(x+map[y][x] <N)dp[y][x+map[y][x]]+=dp[y][x];
                
            }
        }
        
        System.out.println(dp[N-1][N-1]);
        
    }
}
 
 

 

---

index는 정수값..

패키지는빼주고 클래스이름은 Main으로..