본문 바로가기

알고리즘/백준

1890번 : 점프

https://www.acmicpc.net/problem/1890

 

1890번: 점프

문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로

www.acmicpc.net

 

 

이 문제는 기분좋게 풀었다.

 

DP를 이용한 하향식 접근으로 문제를 해결했다. 

 

 


 

 

해설코드(C++).

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstring>
 
using namespace std;
 
long long dp[100][100];
int arr[100][100];
int N;
 
long long solve(int r, int c) {
    if (dp[r][c] != -1)
        return dp[r][c];
 
    if (r == 0 && c == 0)
        return 1;
 
    dp[r][c] = 0;
    for (int i = r - 1; i >= 0; i--) {
        if (arr[i][c] + i == r)
            dp[r][c] += solve(i, c);
    }
 
    for (int i = c - 1; i >= 0; i--) {
        if (arr[r][i] + i == c)
            dp[r][c] += solve(r, i);
    }
 
    return dp[r][c];
}
 
int main(void) {
    freopen("input.txt""r", stdin);
    memset(dp, -1sizeof(dp));
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
    
    cout << solve(N - 1, N - 1<< endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter