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

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

해결 방법

문제를 푸는 방법은  다양하게 있으나, 완전탐색으로 풀 경우 시간초과가 발생한다. 이때는 동적계획법을 사용해야한다. 또다른 triangle 인 tree변수를 만들어서, 그 자리에 올수있는 최대값만 저장하는 방식으로 문제를 푼다.

정수삼각형의 가운데요소는 다양한 경로로 도달할 수 있는데, 그중 가장 큰 값으로 갱신하면서 트리를 한줄씩 검사하는 방법이다. 

 

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

int solution(vector<vector<int>> triangle) {
    
    int answer =0;
    vector<vector<int>> tree ;
    tree.push_back(vector<int>(1,triangle[0][0])); //첫번째요소
    for(int i=0; i<triangle.size()-1; i++){
        tree.push_back(vector<int>(triangle[i+1].size(),0)); //다음열
        
        for(int j=0; j<triangle[i].size(); j++){
            tree[i+1][j] = max(tree[i+1][j],tree[i][j] + triangle[i+1][j]);
            tree[i+1][j+1] = max(tree[i+1][j+1], tree[i][j] + triangle[i+1][j+1]);

        }
        
    }
    
    int idx = triangle.size()-1;
    sort(tree[idx].rbegin(), tree[idx].rend());
    return tree[idx][0];

}