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

(20분) 너무 친절하게 dp로 풀라고 만들어논 문제. 위에서부터 최대값을 계산해서 저장하면서 내려오면 최대값을 알 수 있다.

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

using namespace std;

int solution(vector<vector<int>> triangle) {
	int triSize = triangle.size();
	for (int i = 1; i < triSize; i++) {
		int floorSize = triangle[i].size();
		for (int j = 0; j < floorSize; j++) {
			if (j == 0) { // 왼쪽 끝
				triangle[i][j] += triangle[i - 1][j];
			}
			else if (j == floorSize - 1) { // 오른쪽 끝
				triangle[i][j] += triangle[i - 1][j - 1];
			}
			else {
				triangle[i][j] += max(triangle[i - 1][j - 1], triangle[i - 1][j]);
			}
		}
	}

	int maxNum = 0;
	for (int i = 0; i < triangle[triSize - 1].size(); i++) {
		if (maxNum < triangle[triSize - 1][i]) {
			maxNum = triangle[triSize - 1][i];
		}
	}

	return maxNum;
}