알고리즘 문제해결전략 예제:삼각형 위 최대경로 (ID: TRIANGLEPATH)

[문제 링크]

algospot.com :: TRIANGLEPATH

---

알고리즘 문제해결전략  책에 나와있는 알고리즘과 동일하게 구현하였다.

 

핵심은 아래에서 위로 탐색하면서 최대가 되는 값을 선택하는 것이라고 생각한다.

(y,x) 위치에서 아래칸을 선택할 수 있는 경우는 (y+1, x), (y+1, x+1) 두 가지 경우밖에 존재하지 않기 때문에 두 가지 경우 중 가질 수 있는 최대값이 더 큰 쪽을 선택해야 한다.

아래칸이 가질 수 있는 최대값을 알아야 하기 때문에, 맨 아래에서 위로 탐색하는 것이다.

---

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

int n, triangle[101][101], memo[101][101];

inline int max(const int a, const int b) { return a > b ? a : b; }

int Solution(int y, int x)
{
	if (y == n - 1) return triangle[y][x];

	int& ret = memo[y][x];
	if (ret != -1) return ret;

	return ret = max(Solution(y + 1, x), Solution(y + 1, x + 1)) + triangle[y][x];
}

int main(void)
{
	int testcase;
	cin >> testcase;
	while (testcase--)
	{
		memset(memo, -1, sizeof(memo));
		cin >> n;
		for (int i = 0; i < n; i++)
			for (int j = 0; j <= i; j++)
				cin >> triangle[i][j];

		cout << Solution(0, 0) << endl;
	}
}

알고리즘 200일 프로젝트 - 51 day