1932. 정수 삼각형

1. 해결방법

• Dynamic Programming 문제이다.
• N[floor][a] :: floor층의 a 번째 값을 저장한다. (0<= floor <n,  0<= a < n)
• DP[floor][b] :: floor층의 b 번째 값에서 나올 수 있는 최대 합을 저장한다.
• DP[][]를 계산하는 점화식은 3가지 종류가 나온다. 3가지의 경우로 나눠서 DP[][]를 계산해야 한다. 1) a=0 일 때 2) a = floor 개일 때 3) 그 외 나머지 경우
• 1)의 경우 b=0 이다. DP[floor][b]= DP[floor - 1][b] + N[floor][b]
• 2)의 경우 b=floor 이다. DP[floor][b] = DP[floor - 1][b - 1] + N[floor][b]
• 3)의 경우. DP[floor]b] = max(DP[floor - 1][b], DP[floor - 1][b - 1]) + N[floor][b]

 

2. Solution

// Dynamic Programming
#include <iostream>
#include <algorithm>

#define MAX 500
#define endl "\n"

using namespace std;

int n, answer = -1;
int N[MAX][MAX];
int DP[MAX][MAX];

void Input()
{
    int input;

    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            cin >> N[i][j];
        }
    }
}

void Solution()
{
    DP[0][0] = N[0][0];
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if(j == 0) DP[i][j] = DP[i - 1][j] + N[i][j];
            else if(j == n - 1) DP[i][j] = DP[i - 1][j - 1] + N[i][j];
            else DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - 1]) + N[i][j];
        }
    }

    for(int i = 0; i < n; i++) answer = max(answer, DP[n - 1][i]);

    cout << answer << endl;
}

int main()
{
    Input();
    Solution();

    return 0;
}