[BOJ] 1932. 정수 삼각형 - C++

#include <bits/stdc++.h>
using namespace std;
int arr[502][502];
int d[502][502];
int main() {

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			cin >> arr[i][j];
		}
	}
	d[0][0] = arr[0][0];

	for (int i = 1; i <= n; i++) {

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

	cout << *max_element(d[n], d[n] + n);
}

 

# TIP

dp관점으로 생각할 것

자꾸 앞선 수에서 생각을 못하고 그 전 수에 관점을 두는 방식을 버려야함..