[백준 1932번] 정수삼각형(C++)

아이디어 

일단 dp인건 알것이고, 1,2,3으로 3가지 경우의수로 나눠서 풀었다.

1. 가장 왼쪽 노드 = 이전 층의 가장 왼쪽 노드 dp값 + 가장왼쪽 노드의 board값

2. 중간에 껴있는 노드 = max(자신이 받을 수 있는 이전 층 노드dp값) + 자신의 노드 board값

3. 가장 오른쪽 노드 = 이전층의 가장 오른쪽 노드 dp값 + 자신의 노드 board값

C++풀이

#include <bits/stdc++.h>

using namespace std;
int board[501][501];
int dp[501][501];
int N;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(int i = 0 ; i< N; i++)
    {
        for(int j = 0 ; j<i+1; j++)
        {
            int tmp;
            cin >> tmp;
            board[i][j] = tmp;
        }
    }
    dp[0][0] = board[0][0];
    for(int i = 1 ; i< N; i++)
    {
        for(int j = 0 ; j< i+1; j++)
        {
            if(j ==0){
                dp[i][0] = dp[i-1][0]+ board[i][j];
            }
            else if ( j>0 && j <i)
            {
                dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+board[i][j];
            }
            else if (j == i)
            {
                dp[i][j] = dp[i-1][j-1] + board[i][j];
            }
        }
    }
    int result = INT_MIN;
    for(int i =0; i< N; i++)
    {
        result = max(result, dp[N-1][i]);
    }
    cout << result;
}