[C++] 1932: 정수 삼각형

https://velog.io/@yekim1/C-1149-RGB%EA%B1%B0%EB%A6%AC
RGB 거리와 같은 방식으로 풀었다

점화식

1. 삼각형의 맨 왼쪽에 위치한 경우
   DP[i][j] += DP[i-1][j]
2. 삼각형의 맨 오른쪽에 위치한 경우
   DP[i][j] += DP[i-1][j-1]
3. 그 외의 경우
   DP[i][j] += max(DP[i-1][j], DP[i-1][j-1])

코드

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

vector<int> v[501];

int main() {
	int n, num;

	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			cin >> num;
			v[i].push_back(num);
		}
	}

	if (n >= 2) {
		v[2][0] += v[1][0];
		v[2][1] += v[1][0];
	}

	// 삼각형의 크기가 1인 경우를 고려
	int ans = v[1][0];


	for (int i = 3; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			// 삼각형의 맨 왼쪽
			if (j == 0) v[i][j] += v[i - 1][j];
			// 삼각형의 맨 오른쪽
			else if (j == i - 1) v[i][j] += v[i - 1][j - 1];
			// 나머지 경우
			else v[i][j] += max(v[i - 1][j], v[i - 1][j - 1]);
			
            // 마지막 줄인 경우 ans 갱신 -> if는 필요없을듯???
			if (i == n) { ans = max(ans, v[i][j]); }
		}
	}

	cout << ans;

}