| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 | 
|---|---|---|---|---|---|---|---|
| 480706 | Toinfinity1 | Jump (BOI06_jump) | Java | 0 ms | 0 KiB | 
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Jump2006P6
{
	static class InputReader {
		BufferedReader reader;
		StringTokenizer tokenizer;
		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
		String next() { // reads in the next string
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() { // reads in the next int
			return Integer.parseInt(next());
		}
		public long nextLong() { // reads in the next long
			return Long.parseLong(next());
		}
		public double nextDouble() { // reads in the next double
			return Double.parseDouble(next());
			}
		}
	static InputReader r = new InputReader(System.in);
	static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args)
	{
		int n = r.nextInt();
		BigInteger[][] dp = new BigInteger[n][n];
		int[][] grid = new int[n][n];
		for (int i = 0; i < n; i ++)
		{
			for (int j = 0; j < n; j ++)
			{
				dp[i][j] = new BigInteger("0");
			}
		}
		for (int i = 0; i < n; i ++)
		{
			for (int j = 0; j < n; j ++)
			{
				grid[i][j] = r.nextInt();
			}
		}
		for (int i = n - 1; i >= 0; i --)
		{
			for (int j = n - 1; j >= 0; j --)
			{
				if (grid[i][j] + i <= n - 1)
				{
					dp[i][j] = dp[i+grid[i][j]][j];
				}
				if (grid[i][j] + j <= n - 1)
				{
					dp[i][j] = dp[i][j].add(dp[i][j+grid[i][j]]);
				}
				if (i== n - 1 && j == n - 1)
				{
					dp[i][j] = new BigInteger("1");
				}
				
			}
		}
		pw.println(dp[0][0]);
		pw.close();
	}
}
