[C++][알고리즘] 프로그래머스:: 정수 삼각형

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

프로그래머스

 

stack 을 이용한 DFS 형식으로 풀려고 하다가 망해버린 문제이다.

커닝을 스을쩍 한뒤 풀은 문제.

다음에 기회되면, 망각이 될 때쯤 다시 풀어야 할 듯.

생각보다 간단한데,, 혼자 복잡하게 생각했다.

 

#include <iostream>
#include <vector>
#define MAX_HEIGHT 500
using namespace std;
 
 
int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int answerTriangle[MAX_HEIGHT][MAX_HEIGHT]={0};
    int maxVal=0;
    int triangleHeight = triangle.size();
    int rowLength;
    for(int height=0; height<triangleHeight; height++)
    {
        int rowLength = triangle[height].size();
        for(int hIndex=0;hIndex<rowLength; hIndex++)
        {
            answerTriangle[height][hIndex] = triangle[height][hIndex];
            if(height==0 && hIndex==0)
            {
                continue;
            }
            else if(hIndex==0 || hIndex==rowLength-1)
            {
                answerTriangle[height][hIndex] += answerTriangle[height-1][hIndex];
            }
            else
            {
                maxVal = max(answerTriangle[height-1][hIndex-1],answerTriangle[height-1][hIndex]);
                answerTriangle[height][hIndex] += maxVal;
            }
        }
    }
    for(int hIndex=0; hIndex<triangle[triangleHeight-1].size(); hIndex++)
    {
        answer = max(answer,answerTriangle[triangleHeight-1][hIndex]);
    }
    return answer;
}

위에서 아래로 내려간다는 그림보다는 (이게 내 실수)

한 행씩 내려갈때 마다 위의값을 받아온다라는 생각을 하면 쉽게 푸는 문제였다...