[DP]점프(백준 1890번), 자바(ㅁㅁ)

 

1890번: 점프 (acmicpc.net)

1890번: 점프

 

자료형 표

타입	값의 범위	bit	byte
int	-2(31)~2(31)-1  :~약 20억	32	4
long	-2(63)~2(63)-1	64	8

 

 

1. 메모리 초과 (BFS와 Queue 를 이용해서 풀음)

import java.util.*;

public class Main {
	
	
	public static void main(String[] args){
		
		int[] dx= {0,1};
		int[] dy= {1,0};
		
		long answer=0;
		int N=0;
		Queue<Point> q=new LinkedList<Point>();
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		int[][] d=new int[N][N];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				d[i][j]=sc.nextInt();
			}
		}
		q.add(new Point(0,0));
		
		while(!q.isEmpty()) {
			Point p=q.poll();
			
			for(int i=0;i<2;i++) {
				int num=d[p.x][p.y];
				int px=p.x+dx[i]*num;
				int py=p.y+dy[i]*num;
				
				if(px>=N || py>=N) continue;
				if(d[px][py]==0) answer++;
				else q.add(new Point(px,py));
			}
		}
		
		
		System.out.println(answer);
		
		
	
	}
	static class Point{
		
		private int x;
		private int y;
		
		Point(int x,int y){
			this.x=x;
			this.y=y;
		}
	}
		
}

 

2. 성공(dp이용) -->dp의 자료형은 long!!!!

import java.util.*;

public class Main2 {
	
	
	public static void main(String[] args){
	
		int N=0;
		
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		int[][] d=new int[N][N];
		long[][] dp=new long[N][N];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				d[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]>=1 && d[i][j]!=0) {
					int px=i+d[i][j];
					int py=j+d[i][j];
					if(px<N) dp[px][j]+=dp[i][j];
					if(py<N) dp[i][py]+=dp[i][j];
				}
			}
		}
		System.out.println(dp[N-1][N-1]);
		
	}
}