본문 바로가기

알고리즘 관련/BOJ

BOJ)1890 점프

문제: icpc.me/1890


규칙에 맞게 갈 수 있는 경로가 주어질 때 오른쪽 맨 아래로 가는 경우의 수를 계산해주는 문제이다.


우리는 dp[x][y] = 0,0에서 x,y로 가는 경우의 수로 테이블을 잡아 준 뒤


x,y에서 나보다 x좌표나 y좌표가 작은 지역중 나에게로 올 수 있는 경우의 수를 더해줘서 n^3 다이나믹 프로그래밍으로 구해줄 수 있다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll n, dp[101][101], a[101][101];
ll func(int x, int y) {
    if (x == y&&== 0)return 1;
    ll &ret = dp[x][y];
    if (ret != -1)return ret;
    ret = 0;
    for (int i = x - 1; i >= 0; i--
        if (a[i][y] == x - i)
            ret += func(i, y);
    for (int i = y - 1; i >= 0; i--
        if (a[x][i] == y - i)
            ret += func(x, i);
    return ret;
}
int main() {
    scanf("%lld"&n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            scanf("%lld"&a[i][j]);
    }
    memset(dp, -1sizeof(dp));
    printf("%lld\n", func(n - 1, n - 1));
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)12026 BOJ 거리  (0) 2017.03.01
BOJ)10816 숫자 카드2  (1) 2017.03.01
BOJ)2916 자와 각도기  (0) 2017.03.01
BOJ)3049 다각형의 대각선  (0) 2017.03.01
BOJ)9577 토렌트  (0) 2017.02.22