백준 1932번- 정수 삼각형

문제

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include <numeric>
#include<math.h>
using namespace std;

int main() {
	int n, arr[502][502] = { 0, }, j, max_num = 0;
	cin >> n;
	scanf("%d", &arr[1][1]);
	for (int i = 2; i < n + 1; i++) {
		for (j = 1; j < i+1; j++) {
			scanf("%d", &arr[i][j]);
			arr[i][j] += max(arr[i - 1][j - 1], arr[i - 1][j]);
		}
	}
	for (int i = 1; i < n + 1; i++) {
		if (max_num < arr[n][i])
			max_num = arr[n][i];
	}
	
	cout << max_num;
}

대각선의 값중 큰값을 계속 더해가서 그중 최대값을 출력하는 방식이다.