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

문제 링크

 

풀이

점화식 d[i][j]는 왼쪽 대각선 위인 d[i-1][j-1]와 오른쪽 대각선 위인 d[i-1][j] 중에서 큰 값을 triangle[i][j]와 더해준 값입니다.

 

d[i][j] = max(d[i-1][j-1], d[i-1][j]) + t[i][j]

 

코드

#include <string>
#include <vector>
using namespace std;

int wrap(int a)
{
    return a < 0 ? 0 : a;
}
int solution(vector<vector<int>> triangle) 
{
    int answer = 0;
    int size = triangle.size();
    vector<vector<int>> d(size, vector<int>(size, 0));

    for (int i = 0; i < triangle.size(); ++i)
        for (int j = 0; j < triangle[i].size(); ++j)
            d[i][j] = max(d[wrap(i - 1)][wrap(j - 1)], d[wrap(i - 1)][j]) + triangle[i][j];
    for (int i = 0; i < d[size - 1].size(); ++i)
        answer = max(answer, d[size - 1][i]);
    return answer;
}