[백준/C++] The Triangle

The Triangle

    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.

예제 입력 1

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

예제 출력 1

30

풀이

너무 쉽게 풀려서 깜짝 놀랐다. 나 의외로 강할지도? 이젠 DP문제 껌이랄까…?

바로 아래 아니면 대각선 오른쪽 아래로 내려가면 되므로(배열 상) 내려갈 때마다 재귀호출하고 더 큰걸 골라주면 된다. 메모이제이션을 추가하면 속도도 향상된다.

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

int N;
int D[501][501], arr[501][501];

int DP(int i, int j)
{
	if( i > N) return 0;
	int& ret = D[i][j];
	if(ret != -1) return ret;
	return ret = max(arr[i][j] + DP(i + 1, j), arr[i][j] + DP(i + 1, j + 1));
}

int main()
{
	memset(D, -1, sizeof(D));
	cin >> N;
	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= i; ++j)
			cin >> arr[i][j];

	cout << DP(1, 1);
	return 0;
}

끝