문제 설명
0, 0 에서 N - 1, N -1 로 가는 경우의 수를 모두 구하면 된다.
이동은 오른쪽 또는 아래로만 가능하다.
풀이, 증명
입력과 동시에 답을 구했다. O(N^2)
1. dp[0][0] 은 1 로 초기화 한다.
2. 0,0 에서 오른쪽 또는 아래로 갈 수 있다면 이동한 곳에 값을 dp[0][0] 을 넣어준다.
그러면 각각 1 이 들어가게 된다.
3. for loop 이 돌면서 2 번 0,0 에 i,j 를 대입해서 순서대로 실행하게 되면 마지막 dp[N-1][N-1] 에는 답이 들어가게 된다.
위로 또는 왼쪽으로 못가기 때문에 순서대로 for loop 을 돌면서 답을 구할 수 있다.
왜냐하면 미리 답을 넣어놓고 거기에 도착하는 순간은 모든 경로를 다 확인했기 때문이다. 오른쪽 또는 아래로 갈 수 있는것은 j, i 를 더한다는게 된다.
설명이 부족했지만 알아서 이해하시면 됩니다.
코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.*; | |
| import java.io.*; | |
| /** | |
| * https://www.acmicpc.net/problem/1890 | |
| * BOJ 백준온라인져지 1890 점프 풀이 | |
| */ | |
| public class Main { | |
| private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); | |
| public static void main(String args[]) throws IOException { | |
| BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
| int N = Integer.parseInt(br.readLine()); | |
| int map[][] = new int[N][N]; | |
| long dp[][] = new long[N][N]; | |
| dp[0][0] = 1; | |
| for (int i = 0; i < N; i++) { | |
| StringTokenizer st = new StringTokenizer(br.readLine()); | |
| for (int j = 0; j < N; j++) { | |
| map[i][j] = Integer.parseInt(st.nextToken()); | |
| if (dp[i][j] == 0 || (i == N - 1 && j == N - 1)) continue; // 가지치기 | |
| else { | |
| if (i + map[i][j] < N) dp[i + map[i][j]][j] += dp[i][j]; | |
| if (j + map[i][j] < N) dp[i][j + map[i][j]] += dp[i][j]; | |
| } | |
| } | |
| }; | |
| bw.write(String.valueOf(dp[N - 1][N - 1])); | |
| bw.flush(); | |
| } | |
| } |
문제
N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.
각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.
출력
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.
예제 입력 1
4 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0
예제 출력 1
3
힌트
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 백준온라인져지 10819 차이를 최대로 풀이 (0) | 2018.07.02 |
|---|---|
| BOJ 백준온라인져지 1965 상자넣기 풀이 (0) | 2018.06.29 |
| BOJ 백준온라인져지 4999 아! 풀이 (0) | 2018.06.28 |
| BOJ 백준온라인져지 1991 트리 순회 풀이 (0) | 2018.06.28 |
| BOJ 백준온라인져지 10430 나머지 풀이 (0) | 2018.06.27 |