[BEAKJOON] 4883_삼각그래프_C언어

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

풀이

지금까지 경로의 수나 최소값을 구하는 DP들의 풀이와 재귀 함수의 형태가 대부분 비슷하다. 함수가 시작할 때 빠져나오는 조건과 마지막에 return 사이의 구성을 어떻게 해주냐만 해주면 되는데...이게 어려운 것 같다.

처음에는 N,2 지점까지가면 이 값을 max로 하여 이 값과 비교해가면서 모든 경로를 비교하면서 답을 구했다. 이랬더니...시간 초과가 나버렷다. 나름 DP라고해서 짠건데...ㅜ,ㅠ

생각이 안 나..친구의 설명을 듣고 다시 풀었다.

우선 N,2에 도달 후 return하면서 그 전에 DP배열에 저장된 값과 지금 return된 값중에 최소값으로 DP배열에 저장하면서 올라오는 방법인데...글로 설명하기가 어려다...

중요한건 N,2 목표지점에 도달해서 DP배열을 최소값으로 갱신하면서 올라온다는 것이다. 그러면 1,2에 최소값이 저장되며 이 값을 return하여 출력하면 된다.

제출한 코드.

#include <stdio.h>
int map[100010][5], DP[100010][5];
int N, T;
int dx[] = { -1,0,1,1 }; //좌하, 하, 우하, 우
int dy[] = { 1,1,1,0 };
 
void reset_map(int *, int);//배열 초기화
void reset_DP(int *, int);
 
int MIN(int a, int b)//두 수중 최소값 출력.
{
    return a < b ? a : b;
}
 
 
int dp(int y, int x)
{
    if (DP[y][x] != 200000000)
        return DP[y][x];
 
    if (y == N&&x == 2)
        return map[N][2];
 
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx > 0 && xx <= 3 && yy <= N && yy > 0)
            DP[y][x] = MIN(DP[y][x], dp(yy, xx) + map[y][x]);
    }
    return DP[y][x];
}
 
 
int main()
{
    while (1)
    {
        reset_DP(DP,sizeof(DP)/sizeof(int));
        reset_map(map,sizeof(map) / sizeof(int));
 
        scanf("%d", &N);
        if (N == 0) break;
 
        for (int i = 1; i <= N; i++)
            scanf("%d %d %d", &map[i][1], &map[i][2], &map[i][3]);
 
        printf("%d. %d\n", ++T, dp(1, 2));
    }
    return 0;
}
 
void reset_map(int * arr, int size)
{
    for (int i = 0; i < size; i++)
        arr[i] = -1;
}
 
void reset_DP(int * arr, int size)
{
    for (int i = 0; i < size; i++)
        arr[i] = 200000000;
}