[DP] 1932번 - 정수 삼각형(32일차)

#include <iostream>
//memset 사용
#include <cstring>
//max, max_element 사용
#include <algorithm>
using namespace std;

int main(){
    //정수 삼각형 길이 입력
    int n;
    cin >> n;
    //정수삼각형, dp 2차원 배열 동적 할당
    int **trigle = new int *[n];
    int **dp = new int *[n];

    for(int i=0; i<n; i++){
        trigle[i] = new int[i+1];
        dp[i] = new int[i+1];
        //dp는 0으로 초기화
        memset(dp[i], 0, sizeof(int)*(i+1));
    }
    //정수삼각형 값 입력 
    for(int i=0; i<n; i++){
        for(int j=0; j<=i; j++){
            cin >> trigle[i][j];
        }
    }
    //첫번째 dp의 값을 정수 삼각형의 root 값으로 저장
    dp[0][0] = trigle[0][0];
    //0~n-1줄까지 반복
    for(int i=0; i<(n-1); i++){
        //해당 줄의 길이만큼 반복
        for(int j=0; j<=i; j++){
            //해당 줄의 인덱스의 dp값 + 좌측 대각선 아래 정수값과 좌측 대각선 아래 dp값 중 큰 값을 dp에 저장
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + trigle[i+1][j]);
            //해당 줄의 인덱스의 dp값 + 우측 대각선 아래 정수값과 우측 대각선 아래 dp값 중 큰 값을 dp에 저장
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + trigle[i+1][j+1]);
        }
    }
    //최대값 출력
    cout << *max_element(dp[n-1], dp[n-1]+n);
}