답안 #480708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480708 2021-10-17T22:52:23 Z Toinfinity1 Jump (BOI06_jump) Java 11
100 / 100
290 ms 14508 KB
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class jump
{
	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();
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 8644 KB Output is correct
2 Correct 71 ms 8688 KB Output is correct
3 Correct 67 ms 8376 KB Output is correct
4 Correct 68 ms 8340 KB Output is correct
5 Correct 70 ms 8720 KB Output is correct
6 Correct 89 ms 8572 KB Output is correct
7 Correct 74 ms 8728 KB Output is correct
8 Correct 82 ms 8512 KB Output is correct
9 Correct 95 ms 8720 KB Output is correct
10 Correct 88 ms 8508 KB Output is correct
11 Correct 83 ms 8684 KB Output is correct
12 Correct 84 ms 8556 KB Output is correct
13 Correct 88 ms 8472 KB Output is correct
14 Correct 90 ms 8820 KB Output is correct
15 Correct 108 ms 9068 KB Output is correct
16 Correct 188 ms 10992 KB Output is correct
17 Correct 193 ms 10876 KB Output is correct
18 Correct 225 ms 13000 KB Output is correct
19 Correct 212 ms 12444 KB Output is correct
20 Correct 290 ms 14508 KB Output is correct