#1520 내리막 길

내리막 길 문제는 나올 수 있는 모든 경로의 개수를 구하는 프로그램입니다.

 

일반적으로 이렇게 경우의 수를 물어보는 문제는 동적 계획법(dynamic programming)을 이용하면 풀기 쉬워집니다.

 

문제는 다음과 같습니다.

 

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

1520번: 내리막 길

 

downhill

그러면 어떻게 하면 좋을까요?  상하좌우로 움직일 수 있으니, \((i, j)\)에서의 경우의 수 \(d_{i, j}\)는 주변의 값들의 합으로 나타낼 수 있습니다.

 

\[ d_{i, j} = \sum_{(x, y)~ adjacent~ and~ downhill~to~ (i, j)} d_{x, y} \]

 

그런데 하다보면 같은 위치의 값을 여러번 참조하기 때문에 동적 계획법을 사용토록 합니다.

 

다음은 제가 작성한 소스입니다.  소스는 참조용으로만 봐주세요.

//----------------------------------------------------------------------------------------
//    baekjoon #1520
//        - by Aubrey Choi
//        - created at 2019-09-17
//----------------------------------------------------------------------------------------
#include <stdio.h>

int v[502][502], dp[502][502];
int getcase(int r, int c)
{
    if(dp[r][c]!=-1) return dp[r][c];
    if(r==1&&c==1) return dp[r][c]=1;
    int sum = 0;
    if(v[r-1][c]>v[r][c]) sum += getcase(r-1,c);
    if(v[r+1][c]>v[r][c]) sum += getcase(r+1,c);
    if(v[r][c-1]>v[r][c]) sum += getcase(r,c-1);
    if(v[r][c+1]>v[r][c]) sum += getcase(r,c+1);
    return dp[r][c] = sum;
}

int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&v[i][j]), dp[i][j]=-1;
    printf("%d\n", getcase(n,m));
}