동적 계획법 - 3. 삼각형 위의 최대 경로

문제 : 삼각형 위의 최대 경로 (난이도 下)

 

https://algospot.com/judge/problem/read/TRIANGLEPATH

 분석

문제를 보며 처음 든 생각은 '최대합을 반환하면 되지 않을까?'였다.

하지만 생각해보면 최대합을 memoization으로 처리하기엔 배열의 크기가 너무 커진다.

또한 최대합을 구하는데 굳이 최대합을 반환할 필요가 없다.

부분합을 구해 return 해주면 cahce 배열의 크기도 해결할 수 있고, 속도적인 면에서도 이득을 본다.

 

Memoization 참조

2020/11/26 - [알고리즘 문제 해결 전략] - 동적 계획법 (Dynamic Programming)

동적 계획법 (Dynamic Programming)

 

 구현

int n, trianlge[100][100];
int cache[100][100];
int findPath(int y, int x)
{
	//base case 맨 아래 줄
	if (y == n - 1) return trianlge[y][x];
	//memoization
	int& ret = cache[y][x];
	if (ret != -1) return ret;
	return ret = max(findPath(y + 1, x + 1), findPath(y + 1, x)) + trianlge[y][x];
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		memset(cache, -1, sizeof(cache));
		cin >> n;
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x < y + 1; x++)
			{
				cin >> trianlge[y][x];
			}
		}
		cout << findPath(0, 0) << '\n';
	}
	return 0;
}