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

<문제 소개>

---

<소스 코드>

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    for (int i = triangle.size() - 1; i > 0; i--)
	{
		for (int j = 0; j < triangle[i].size() - 1; j++)
		{
			// 하위 두개의 원소 중 큰 원소를 윗단 원소에 더해줌
			int left = triangle[i][j];
			int right = triangle[i][j + 1];

			triangle[i - 1][j] += max(left, right);
		}
	}

	answer = triangle[0][0]; // root 노드의 값이 최대값이 됨  
    
    return answer;
}

---

<풀이과정>

1. 삼각형의 가장 밑의 노드들부터 이웃한 노드를 두 개씩 묶어서 더 큰 값을 바로 위의 노드에 더해주는 과정을 반복하여 root 노드까지 올라가면 해당 값이 최대값이 된다.

2. 그러므로 먼저 가장 밑의 노드들부터 root 직전 노드들까지 반복하며 이웃한 원소 triangle[i][j]와, triangle[i][j+1]을 비교하여 더 큰 값을 위의 노드인 triangle[i-1][j]에 더해준다.

3. 위 과정을 반복한 뒤 root 노드의 값을 answer에 대입해준다.

---

<코멘트>

처음에 DFS로 풀었다가 시간초과가 와다다 났다ㅋㅋㅎㅋ

좀 더 생각해보니 DP로 풀 수 있는 문제였다.

bottom-up 방식으로 진행하였다.(근데 이게 DP 문제가 맞나..?)

---

<제출결과>