BOJ[백준] - 1520 - 내리막 길
https://www.acmicpc.net/problem/1520
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 |
#include <stdio.h>
int dp[501][501], a[501][501], N, M, i, j;
int nx[] = { 1,-1,0,0 }, ny[] = { 0,0,1,-1 };
int solve(int x, int y)
{
int ret = 0;
if(x == 0 || y == 0)
return 0;
if(x == N && y == M)
return 1;
if(dp[x][y] != -1)
return dp[x][y];
for(int i = 0; i < 4; i++)
if(a[x][y] > a[x + nx[i]][y + ny[i]])
ret += solve(x + nx[i], y + ny[i]);
return dp[x][y] = ret;
}
int main()
{
scanf("%d %d", &N, &M);
for(i = 1; i <= N; i++)
for(j = 1; j <= M; j++)
scanf("%d", &a[i][j]),dp[i][j]=-1;
printf("%d", solve(1,1));
return 0;
} |
cs |
'Algorithm 문제풀이 > BOJ [백준] 문제풀이' 카테고리의 다른 글
BOJ[백준] - 1720 - 타일 코드 (0) | 2017.07.15 |
---|---|
BOJ[백준] - 1699 - 제곱수의 합 (0) | 2017.07.15 |
BOJ[백준] - 1509 - 팰린드롬 분할 (0) | 2017.07.15 |
BOJ[백준] - 1495 - 기타리스트 (0) | 2017.07.15 |
BOJ[백준] - 1463 - 1로 만들기 (0) | 2017.07.15 |