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

정수 삼각형 문제 설명

풀이 과정

1. 현재의 숫자에서 그 윗줄의 숫자를 더하는 방식

2. 배열의 길이가 각 열마다 다르기 때문에 0과 triangle[i].size()-1은 따로 조건을 빼주기

3. 위의 범위에 해당하지 않는 j는 윗줄의 좌,우를 비교해보기 

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = triangle[0][0];
    int index=0;
    for(int i=1;i<triangle.size();i++){
        for(int j=0;j<triangle[i].size(); j++){
                if(j==0)
                    triangle[i][j]+=triangle[i-1][j];
                else if(j==triangle[i].size()-1)
                  triangle[i][j]+=triangle[i-1][j-1];   
                else
                  triangle[i][j]+=max(triangle[i-1][j-1], triangle[i-1][j]); 
           
                answer=max(answer, triangle[i][j]);
        }
    }
    
    
    return answer;
}