[백준] 1890 점프 - Dynamic Programming / Java

• 문제 링크

1890번: 점프

 

• 풀이 과정

이 문제의 경우 게임판과 메모이제이션할 배열을 따로 입력받지 않아도 풀이가 가능하다.

우선 n + 1 * n + 1 크기의 dp 배열을 생성하고 dp[1][1] = 1 로 시작점을 초기화한다.

 

반복문에서 dp[i][j] 가 0일 경우, 해당 위치로 이동 가능한 경우의 수가 1개 이상이 아님을 의미하므로 처리하지 않는다.

입력받은 dist 값은 현재 위치에서 이동 가능한 거리이며 우측, 하단 방향으로 그 거리만큼 이동했을 때

배열의 크기 n을 넘지 않을 경우 이동할 위치에 dp[i][j], 즉 현재 위치까지 이동 가능 경우의 수를 더해준다.

 

최종적으로 종착점 dp[n][n] 에 모든 이동 가능 경우의 수가 누적된 결과가 출력된다.

 

• 풀이 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		long dp[][] = new long[n + 1][n + 1];
		dp[1][1] = 1;

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				int dist = Integer.parseInt(st.nextToken());

				if (dp[i][j] >= 1 && dist != 0) {
					if (j + dist <= n)
						dp[i][j + dist] += dp[i][j];
					if (i + dist <= n)
						dp[i + dist][j] += dp[i][j];					
				}
			}
		}

		bw.write(dp[n][n] + "\n");
		bw.flush();
	}

}