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

문제

삼각형이 주어지고 위에서 아래로 내려오는데, 이때 그냥 내려오거나 오른쪽 대각선으로 내려가야만 한다.

 

이런 상황에서 합이 최대가 되는 경로에 있는 수의 합을 출력해라.

 

입력

첫째 줄에 삼각형의 크기 n(1 <= n <= 500)이 주어지고 둘째 줄부터 n개의 줄에 정수 삼각형이 주어진다.

 

예제 입력

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

예제 출력

30

문제 해결

어디서 힌트를 얻을 수 있을까?

 

'최대 합', '경로', '이동 방향성'이라는 키워드를 보고 이 문제는 브루트포스로도 풀 수 있겠다라는 생각을 했다.

 

하지만 브루트포스로 문제를 풀 경우 중복되는 부분 문제의 수가 많기 때문에 이를 해결하기 위해 다이나믹 프로그래밍을 적용해서 풀기로 했다.

 

단순히 다이나믹 프로그래밍을 구현할 수 있냐의 문제이므로 코드는 다음과 같다.

코드

#include <iostream>

int cache[501][501];
int board[501][501];

int dp(int N, int y, int x)
{
	if (N == 0)
		return 0;
	int& ret = cache[y][x];
	if (ret != -1)
		return ret;
	return ret = std::max(dp(N - 1, y + 1, x) + board[y][x], dp(N - 1, y + 1, x + 1) + board[y][x]);
}

int main(void)
{
	int N;
	std::cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < i + 1; j++)
			std::cin >> board[i][j];
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cache[i][j] = -1;
		}
	}
	std::cout << dp(N, 0, 0) << std::endl;
	return 0;
}