[백준 1890번] 점프 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

문제에서 주어진 내용을 보면 게임의 점프 진행은 언제나 왼쪽에서 오른쪽 위쪽에서 아래쪽으로 진행됩니다.

 

하여 DP의 진행 또한 왼쪽에서 오른쪽으로 위쪽에서 아래쪽으로 진행을 하면 문제를 풀 수 있습니다.

 

DP의 각각의 위치에는 말이 시작점에서 점프되어 온 경우의 수를 가지고 있습니다.

 

예제를 통해 문제를 풀면 맨 처음 움직일 수 있는 (1, 1)(가장 왼쪽의 가장 위쪽)은 어떤 게임이 되어도 1이 되어야 합니다.

 

해당 부분은 시작점이므로 무조건 해당 부분에서 이동이 일어나기 때문입니다.

 

아래 표처럼 DP가 준비됩니다.

1	0	0	0
0	0	0	0
0	0	0	0
0	0	0	0

그다음은 (1, 1) 위치에서 DP[1][1]만큼 오른쪽과 아래쪽으로 이동된 곳은 출발 지점의 수만큼 증가하게 됩니다.

※ 출발 지점의 수만큼 증가시키는 이유는 출발 지점의 DP가 5인 경우는 해당 출발지점까지 오는 경우의 수가 5가지 이므로 해당 출발 점에서 다음 위치로 이등 가능한 경우의 수 또한 5가지 존재하기 때문입니다.

 

DP는 아래 표처럼 됩니다.

1	0	1	0
0	0	0	0
1	0	0	0
0	0	0	0

이제 DP를 왼쪽에서 오른쪽으로 위쪽에서 아래쪽으로 반복하면서 0이 아닌 경우 점프를 또 진행합니다.

 

DP가 0인 경우는 해당 위치는 최초 시작점에서 점프하여 올 수 없는다 것을 의미하므로 처리가 필요 없습니다.

 

2번의 점프를 진행하면 DP는 아래 표처럼 됩니다.

1	0	1	0
0	0	0	0
1	1	0	0
1	0	1	0

 

3번의 점프를 진행하면 DP는 아래 표처럼 됩니다.

1	0	1	0
0	0	0	0
1	1	0	1
1	0	1	2

 

4번의 점프를 진행하면 DP는 아래 표처럼 됩니다.

1	0	1	0
0	0	0	0
1	1	0	1
1	0	1	3

 

6. 코드

전체 코드는 Git에 있습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stringTokenizer;

int num = Integer.parseInt(br.readLine());

long[][] dp = new long[num+1][num+1];

dp[1][1] = 1;

for(int i=1; i<=num; i++){
	stringTokenizer = new StringTokenizer(br.readLine());

	for(int j=1; j<=num; j++){
		int moveLength = Integer.parseInt(stringTokenizer.nextToken());

		if(dp[i][j] >= 1 && moveLength != 0) {
			if (j + moveLength <= num)
				dp[i][j + moveLength] += dp[i][j];

			if (i + moveLength <= num)
				dp[i + moveLength][j] += dp[i][j];
		}
	}
}

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