[BEAKJOON]1520_내리막길_C언어

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

풀이

예전에 푼 문제이나 오늘 내리막길과 완~~전 비슷한 점프를 풀어서 포스팅하는김에 같이 올린다. 이 문제는 내가 처음으로 DP라는 것을 알게 되었고 메모이제이션이라는 단어를 처음 들어본 문제이다.

단순한 탐색으로 풀면은 시간초과가난다. 좀 설명하기 어려운데...나름 자세히 설명을 하겠다.

1. 해당 y x 좌표에서 현재 위치에서 작은 값으로 진행을 하면서 나아간다.

2. 이렇게 작은 수로 나아가다가 y==N,x== N 지점이 되면 return 1;을 한다.

3. y==N, x==N가 return되면 리턴된 값을 DP배열에 저장하고 이 함수는 DP배열을 return한다.

4. 이렇게 상하좌우로 갈라지는 지점에서 그 경로에서 N,N까지 가는 경로들이 더해지면서 시작 지점 0,0 혹은 1,1에서 N,N까지 가는 경로의 수가 대입된다.

문제에서 주어진 예제에서 DP배열이 변하는 과정을 캡쳐했습니다. 설명이 좀 이상하지만...해당 지점에서 경로의 수를 return해주면서 갈라지는 분기점에서는 return되는 값이 합해지는걸 볼 수 있습니다.

제출한 코드

#include <stdio.h>
#include <string.h>
 
int map[500][500] = { 0 };
int dp[500][500] = { 0 };
int hh[4] = { -1,1,0,0 };
int ww[4] = { 0,0,-1,1 };
int h, w;
 
int dspdp(int y, int x, int max)
{
    if (dp[y][x] != -1) return dp[y][x];    
    if ((y == h-1) && (x ==w-1)) return 1;
 
 
    dp[y][x] = 0;
 
    for (int i = 0; i < 4; i++)
    {
        if (max>map[y + hh[i]][x + ww[i]] && y + hh[i]<h&&x + ww[i]<w && (y + hh[i]) >= 0 && (x + ww[i]) >= 0)
       //다음 값이 전 값보다 작으면서 위치가 입력받은 map의 범위에 속하는지
        {
 
            dp[y][x] += dspdp(y + hh[i], x + ww[i], map[y + hh[i]][x + ww[i]]);
        }
    }
 
    return dp[y][x];
}
 
int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%d %d", &h, &w);
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
 
    printf("%d\n", dspdp(0, 0, map[0][0]));
 
    return 0;
}