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

풀이

dp 문제였다
위에서 아래로 내려가면서 지나가는 경로의 수를 더한 값의 최대값을 구하는 문제이다.
위에서 아래로 더하지 않고 아래서 위로 더해서 구하였다.

i,j에 있는 값에 i+1,j 의 최댓값과 i+1,j+1의 최댓값중 더 큰 값을 더한 값은 i,j를 지나는 순간 부터 얻을 수 있는 값중 제일 큰 값이다.
이렇게 더하다보면 0,0에 제일 큰 값이 들어가게 된다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;

    int triangle_size = triangle.size();
    int triangle_c_size = triangle.size();
    for(int i=triangle_size-1;i>0;i--,triangle_c_size--){
        for(int j = 0;j<triangle_c_size-1; j++ ){
            triangle[i-1][j] = max(triangle[i][j],triangle[i][j+1]) + triangle[i-1][j];
        }

    }

    answer = triangle[0][0] ;
    return answer;
}