[백준] 1932번 정수 삼각형 C++ 문제풀이

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

문제 풀이

최대가 되는 경우를 구해야하므로 그리디 아니면 DP로 풀어야겠다고 생각을 했다.

dp[1][1] = 7, dp[2][1] = 3+7, dp[2][2] = 8+7 이고,  

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + (현재 위치의 값)이라는 점화식을 통해 문제를 해결했다.

소스 코드

#include <iostream>
using namespace std;

int tree[501][501] = { 0 };
int dp[501][501] = { 0 };

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> tree[i][j];
		}
	}
	dp[1][1] = tree[1][1];
	dp[2][1] = tree[2][1] + tree[1][1];
	dp[2][2] = tree[2][2] + tree[1][1];
	for (int i = 3; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + tree[i][j];
		}
	}
	
	int max_num = 0;

	for (int i = 1; i <= n; i++) {
		max_num = max(dp[n][i], max_num);
	}
	cout << max_num << '\n';
}