BAEKJOON 1932 - 숫자삼격형

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

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5 (Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.

• Each step can go either diagonally down to the left or diagonally down to the right.
• The number of rows in the triangle is ≥ 1 but ≤ 500.
• The numbers in the triangle, all integers, are between 0 and 9999 (inclusive).

입력

Data about the number of rows in the triangle are first read from the input.

출력

The highest sum is written as an integer in the output.

예제 입력 

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 

30

힌트

출처

Olympiad > International Olympiad in Informatics > IOI 1994 1번

이전에 풀어본적이 있는 문제네요. 밑에서부터 더해가며 memoization을 이용해 풀 수 있습니다.

#pragma warning (disable:4996)
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
 
const int MAX = 500;
int numbers[MAX][MAX];
int cache[2][MAX];
 
int dp(int n)
{
    for (int x = 0; x < n; x++)
    {
        cache[(n - 1) % 2][x] = numbers[n - 1][x];
    }
 
    for (int y = n - 2; y >= 0; y--)
    {
        for (int x = 0; x < y + 1; x++)
        {
            cache[y % 2][x] = max(cache[(y + 1) % 2][x], cache[(y + 1) % 2][x + 1]) + numbers[y][x];
        }
    }
 
    return cache[0][0];
}
 
 
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            scanf("%d", &numbers[i][j]);
        }
    }
 
    printf("%d\n", dp(n));
 
    return 0;
}