[BAEKJOON] 1932_숫자삼각형_C언어

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

풀이

우선 이 문제는 DP문제이다. 그냥 배열이 주어지고 특정 방향을 따라 최대 최소 경로의 수 를 구하는 문제들은 삘링이 그냥 DP같아서...별 생각없이 DP로 먼저 생각하게 된다.

이 정도 난이도의 DP문제는 다 비슷비슷한 거 같다. 최근에 풀었던 삼각 그래프나 기업투자와 유형과 접근이 비슷해 금방 풀었던 것 같다.

1. arr의 맨 아래 삼각형 밑 면까지 모든 경로를 탐색하며 내려간다.

2. 밑 면에 도착하면 해당 밑면의 arr배열의 값을 return해준다.

3. return된 값과 맨 밑면에 도달하기 전 위치의 arr값을 더해준 뒤 DP배열에 저장한다.

4. 모든 밑면에 대하여 3번과 같은 단계를 거치며 return될 때마다 그 전에 DP배열에 저장된 값과 다른 경로로 return된 값과 arr값을 더한 값 중에 더 큰 값으로 DP 배열에 저장한다.

3번과 4번 과정을 삼각형의 맨 위에 도달할 때 까지 계속한다. 그러면 DP배열의 맨 위에 최대값이 저장된다.

그림??배열이 변하는 과정??은...아마도 삼각 그래프에 사진을 올려 놓았을 것이니 삼각 그래프를 참조하세요!!

제출한 코드

#include <stdio.h>
#include <string.h>
int n, arr[550][550], DP[550][550];
int dx[] = { 0,1 }, dy[] = { 1,1 };
 
int MAX(int a, int b)
{
    return a < b ? b : a;
}
 
int dp(int y, int x)
{
    if (y == n)
        return arr[y][x];
 
    if (DP[y][x]!=-1)
        return DP[y][x];
 
    for (int i = 0; i < 2; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (arr[yy][xx] != -1)
            DP[y][x] = MAX(DP[y][x], dp(yy, xx) + arr[y][x]);
    }
 
    return DP[y][x];
}
 
int main()
{
    memset(arr, -1, sizeof(arr));
    memset(DP, -1, sizeof(DP));
    scanf("%d",&n);
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d",&arr[i][j]);
 
    printf("%d\n",dp(1,1));
 
    return 0;
}