백준_1932_정수 삼각형

다이나믹 프로그래밍(dp) 문제였다. 점화식을 세울 때 규칙을 잘 생각해봐야했다.

삼각형에서 제일 왼쪽 수, 제일 오른쪽 수, 가운데에 있는 수들 이 각각 다른 점화식을 갖는다.

윗단에서 선택한 숫자의 위치가 밑단에서 선택할 수 있는 숫자의 위치에 영향을 주기 때문이다. (왼쪽, 오른쪽 대각선)

#include <iostream>
#include <algorithm>
#define MAX 501

using namespace std;

int n, d[MAX][MAX], arr[MAX][MAX], answer;

void dp() {
	d[1][1] = arr[1][1];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			if (j == 1) { // 삼각형에서 제일 왼쪽 수
				d[i][j] = d[i - 1][j] + arr[i][j];
			}
			else if (j == i) { // 삼각형에서 제일 오른쪽 수
				d[i][j] = d[i - 1][j - 1] + arr[i][j];
			}
			else { // 삼각형에서 가운데 수들
				d[i][j] = max(d[i - 1][j], d[i - 1][j - 1]) + arr[i][j];
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		answer = max(answer, d[n][i]);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> arr[i][j];
		}
	}
	dp();
	cout << answer << '\n';
	return 0;
}