코테/백준
[백준/JAVA] 1890번: 점프
imname1am
2023. 5. 28. 21:01
반응형
🔺 문제
1890번: 점프
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[][] map = new int[N + 1][N + 1];
// 입력 받기
for(int i = 1 ; i <= N ; i++) {
st = new StringTokenizer(br.readLine()," ");
for(int j = 1 ; j <= N ; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// DP 배열 채우기
long[][] dp = new long[N + 1][N + 1];
dp[1][1] = 1;
for(int i = 1 ; i <= N ; i++) {
for(int j = 1 ; j <= N ; j++) {
int next = map[i][j];
if(i == N && j == N) continue;
// 오른쪽으로 이동
if(j + next <= N)
dp[i][j + next] += dp[i][j];
// 아래쪽으로 이동
if(i + next <= N)
dp[i + next][j] += dp[i][j];
}
}
System.out.println(dp[N][N]);
}
}
|
cs |
✅ 해결 아이디어
✔ DP
1) 테이블 정의
- dp[i][j] = (i, j) 위치 까지 도착하는 경우의 수
2) 점화식 찾기
- 오른쪽으로 이동하는 경우 : dp[ i ] [ j+ map[i][j] ] += dp[i][j]
- 아래로 이동하는 경우 :dp[i + map[i][j] ] [ j ] += dp[i][j]
3) 초기값 설정
-dp[1][1] = 1;
🔺 다른 풀이들
- dp 배열 채우는 부분이 조금 다르심
[BOJ] 백준 1890번 : 점프 (JAVA)
문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거
steady-coding.tistory.com
💬 느낀 점
점화식 찾아놓고 헤매고 있던 나 바보....
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 240309 |
(+ 240309 2회독 : 14300KB, 124ms)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int[][] board;
static long[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
board = new int[N+1][N+1];
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0 ; j < N ; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
dp = new long[N+1][N+1];
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) continue;
int val = board[i][j];
// 오른쪽으로 이동
if(j + val < N)
dp[i][j + val] += dp[i][j];
// 아래쪽으로 이동
if(i + val < N)
dp[i + val][j] += dp[i][j];
}
}
System.out.println(dp[N-1][N-1]);
}
}
|
cs |
(참고)
✔ 과정 설명 굿... 놓친 부분을 깨달았습니다 감사합니다....
[JAVA] 백준 1890번 : 점프
hu-coding.tistory.com
반응형