2019-03-22 [JAVA]백준 1890번 - 점프
22 Mar 2019 | java algorithm_study문제 출처
https://www.acmicpc.net/problem/1890
문제 접근(실패)
- Queue를 이용하기
- 0,0 부터 시작하여 점프가능한 곳을 큐에 넣고 도착 지점 개수 세기
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Baekjoon_1890 {
static int n;
static Jump[][] map;
static int count = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
map = new Jump[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = new Jump(j, i, sc.nextInt());
}
}
dp(0, 0);
System.out.println(count);
}
public static void dp(int x, int y) {
Queue<Jump> q = new LinkedList<>();
q.offer(map[y][x]);
while (!q.isEmpty()) {
Jump tmp = q.poll();
if (tmp.y == n-1 && tmp.x == n-1) {
count++;
continue;
}
if (tmp.value + tmp.y < n) {
q.offer(map[tmp.value + tmp.y][tmp.x]);
}
if (tmp.value + tmp.x < n) {
q.offer(map[tmp.y][tmp.value + tmp.x]);
}
}
}
}
class Jump {
int x, y;
int value;
Jump(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
}
=> 메모리, 시간 초과
문제 접근
-
다이나믹 프로그래밍
- 행 마다 가로로 갈 수 있는 경우 체크 -> 열마다 세로로 갈 수 있는 경우 체크
- 반복
import java.util.Scanner;
public class Baekjoon_1890 {
static int[][] map;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
map = new int[n][n];
long[][] dp = new long[n][n];
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
map[i][j] = sc.nextInt();
dp[0][0] = 1;
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
//행 마다 가로로 갈 수 있는 경우 체ㅋㅡ
if(dp[i][j] != 0 ){
if(map[i][j]+j<n){
if(j == n-1)
break;
if(map[i][j]!= 0)
dp[i][map[i][j]+j] +=dp[i][j];
else
dp[i][j] = 0;
}
}
}
//열마다 세로로 갈 수 있는 경우 체크
for (int j=0; j<n; j++){
if(dp[i][j] != 0){
if(map[i][j]+i<n){
if(i == n-1)
break;
if(map[i][j]!= 0)
dp[map[i][j]+i][j] +=dp[i][j];
else
dp[i][j] = 0;
}
}
}
}
System.out.println(dp[n-1][n-1]);
}
}
Comments