백준 C++ - 정수삼각형(1932) DP

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

1932번: 정수 삼각형

1. n-1 층에서부터 두 방향 중 가장 큰 수를 가진 방향을 선택하여 더합니다.

 

1) 입력

7
3	8
8	2	0

 

2) n-1층부터 아래층의 큰 수를 선택하여 더함

7
11	10
8	2	0

 

3) 배열 (1,1) 위치엔 최댓값이 들어가 있습니다.

18
11	10
8	2	0

 

#pragma warning(disable:4996)
#include <stdio.h>
#include <algorithm>
using namespace std;
int arr[501][501];
int n;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			scanf("%d", &arr[i][j]);

	for (int i = n - 1; i >= 1; i--)
		for (int j = 1; j <= i; j++)
			arr[i][j] += max(arr[i + 1][j], arr[i + 1][j + 1]);

	printf("%d", arr[1][1]);
}