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

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

1932번: 정수 삼각형

 최초풀이

위에서부터 아래로 규칙에 따라 최대 값을 갱신해가는 배열을 만듭니다.

가장 아래 단계까지 구했다면 그 단계의 최대 값을 출력해 줍니다.

#include <iostream>

using namespace std;

int dp[501][501];

int main() {
	int n, temp;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			cin >> temp;
			if (j == 0)
				dp[i][j] = temp + dp[i - 1][j];
			else if (j == i - 1)
				dp[i][j] = temp + dp[i - 1][j - 1];
			else {
				if(dp[i-1][j-1]>dp[i-1][j])
					dp[i][j] = temp + dp[i - 1][j - 1];
				else
					dp[i][j] = temp + dp[i - 1][j];
			}
		}
	}

	int max = 0;// 정답출력

	for (int i = 0; i < n; i++) {
		if (dp[n][i] > max)
			max = dp[n][i];
	}

	cout << max;
	
	return 0;
}