[프로그래머스]정수삼각형

문제요약

정수로 구성된 삼각형이 있습니다.
맨 위에서 시작해서 맨 아랫단에 도달할 때, 가장 큰 정수의 합은 무엇일까요??

의역

삼각형 모양 맵에 보상이 흩뿌려져있다. 한 번 앞으로 갈 때 좌우 컨트롤밖에 안되는 플레이어가 있다. 앞으로 나아가며 삼각형 밑단에 도달했을 때 받을 수 있는 보상의 최대값은??

아이디어

DP) 윗 단이 안정화되면 아랫단의 DP를 안정적으로 구할 수 있다.

코드

12분컷

#include <string>
#include <vector>
#include<math.h>
#include<memory.h>
using namespace std;
int tab[500][500];

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    memset(tab,0, sizeof(tab));
    int n = triangle.size();
    tab[0][0] = triangle[0][0];
    for(int i = 0;i<n-1;i++){//내가 영향을 주는 것
        for(int j = 0;j<=i;j++){
            tab[i+1][j] = max(tab[i+1][j], tab[i][j]+triangle[i+1][j]);
            tab[i+1][j+1] = max(tab[i+1][j+1],tab[i][j]+triangle[i+1][j+1]);
        }
    }
    //맨 마지막단을 검사
    int max_d = 0;
    for(int j = 0;j<n;j++){
        max_d= max(max_d, tab[n-1][j]);
    }
    answer= max_d;
    return answer;
}