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

링크

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

코딩테스트 연습 - 정수 삼각형 | 프로그래머스

풀이

삼각형의 이동 방향은 왼쪽, 오른쪽으로 이동 한다. 

이때 왼쪽 끝과 오른쪽 끝에 있는 정수는 항상 바로 위 한개의 정수를 통해서 올수 있고

나머지 가운데 있는 정수는 왼쪽 오른쪽에서 올수 있기 때문에 

조건을 3가지로 나누었다.

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

long long dp[550][550];

int solution(vector<vector<int>> triangle) {
	int t_size = triangle.size();

	dp[0][0] = triangle[0][0];

	for (int i = 1; i < t_size; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0)
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			else if (j == i)
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
		}
	}

	long long res = 0;
	for (int i = 0; i < t_size; i++) {
		res = max(res, dp[t_size - 1][i]);
	}
	return res;
}