백준_1890 점프(자바) / DP

시간 & 메모리 제한

문제

입력 & 출력

 

DP를 이용한 문제 풀이

package com.Back;

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

public class Back_1890 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int[][] map = new int[N][N];
		long[][] dp = new long[N][N];
		
		for (int i = 0; i < N; i++) {
			st= new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		dp[0][0]=1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(i==N-1 && j == N-1)break;
				else {
					int right = j + map[i][j];
					int down = i + map[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-1][N-1]);
	}

}

 

- 처음에는 DFS를 이용해서 문제풀이를 진행했었습니다... 잘 안풀려서 DP로 시도 했더니 쉽게 풀렸습니다.

 

- DP를 이용해서 문제 풀이를 진행했습니다... 그래서 map이라는 배열과 동시에 dp라는 배열을 만들었습니다.

 

- 이중 for문을 통해서 이동 가능한지를 dp를 통해서 체크를 해줍니다.

 

- 오른쪽으로 가는 경우와 아래로 가는 경우만 체크해 주면 되기 때문에 좀 수월하게 풀 수 있습니다.

 

- 2번 당했더니 이부분은 꼼꼼하게 잘 체크 했던거 같습니다... 바로 long형 쓰는거 잊으면 안됩니다.

2^63-1까지 표현 할수 있다는 것은 long형!