[C++] 백준 1932. 정수 삼각형

🌽 문제

🥕 입출력

🥔 풀이

가에 있는 애들은 바로 위에 있는 애들로만 더해지고,
중간에 껴있는 애들은 위의 두 수 중 더 큰 수와 더해가면 된다.
계산이 끝나면 마지막줄을 돌며 가장 큰 수의 합을 구하여 출력한다.

🥬 코드

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, maxi = 0;
	int dp[500][500] = { 0, };

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= i; j++)
			cin >> dp[i][j];

	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0) dp[i][j] = dp[i - 1][0] + dp[i][j];
			else if (i == j) dp[i][j] = dp[i - 1][j - 1] + dp[i][j];
			else dp[i][j] = dp[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j]);
		}
	}
	
	for (int i = 0; i < n; i++) {
		maxi = max(maxi, dp[n - 1][i]);
	}
	cout << maxi;
	return 0;
}

🥜 채점