[C][백준] 1932. 정수 삼각형 구현하기 | Dynamic Programming

#include <stdio.h>
#define MAX_NUM 505

int main(void)
{
    int table[MAX_NUM][MAX_NUM] = {0};
    int dp[MAX_NUM][MAX_NUM] = {0};
    int num;
    scanf("%d", &num);

    // 입력
    for (int i = 1; i <= num; i++)
    {
        for (int j = 0; j < i; j++)
        {
            scanf("%d", &table[i][j]);
        }
    }

    // dp 테이블 끝 요소 채우기
    dp[1][0] = table[1][0];
    for (int i = 2; i <= num; i++)
    {
        dp[i][0] = dp[i - 1][0] + table[i][0];
        dp[i][i - 1] = dp[i - 1][i - 2] + table[i][i - 1];
    }

    // dp
    for (int i = 3; i <= num; i++)
    {
        for (int j = 1; j < num; j++)
        {
            int left = dp[i - 1][j - 1];
            int right = dp[i - 1][j];

            if (left <= right)
            {
                dp[i][j] = table[i][j] + right;
            }
            else
            {
                dp[i][j] = table[i][j] + left;
            }
        }
    }

    // 맨 마지막 줄 중 가장 큰 수
    int result = 0;
    for (int k = 0; k < num; k++)
    {
        if (result < dp[num][k])
            result = dp[num][k];
    }

    printf("%d", result);

    return 0;
}

맨 위층에서 아래층까지의 합이 최대가 되는 경로를 구하는 문제이다.

 

이 문제는 DP로 풀어야한다. DP 문제를 다차원배열 단원에서 풀어야 한다니... ㄷㄷ

 

DP 테이블 끝 요소 채우는 것은 괜히 만든 것 같다.