백준 1932번: 정수 삼각형

[문제 링크]

1932번: 정수 삼각형

---

https://onlytrying.tistory.com/61

알고스팟의 삼각형 위 최대경로 문제와 유사한 문제였다.

 

TopDown으로 푸는 경우 현재 위치(Y, X)에서 다음 위치로 가는 경우가 (Y-1, X-1)과 (Y-1, X)만 존재하기 때문에 (Y-1, X-1) 이 가질 수 있는 최대값과 (Y-1, X) 이 가질 수 있는 최대값을 비교하여 더 큰 경우를 선택하면 된다.

함수를 재귀 호출하는 방법으로 이를 구현할 수 있으며, 기저사례로 X가 범위에 속하지 않을 경우 0을 반환하고, Y가 0일 때 즉, 삼각형의 꼭대기에 도달했을 때 그 위치의 정수값을 반환하도록 하였다.

 

BottomUp으로 푸는 경우 현재 위치(Y, X)가 가질 수 있는 최대값은 (Y-1, X-1)의 최대값과 (Y-1, X)의 최대값 중 더 큰 값에 현재 위치(Y, X)의 정수값을 더해줌으로써 구할 수 있다. 

TopDown과 마찬가지로 X가 범위에 속하지 않는 경우 최대값이 존재할 수 없기 때문에 계산하지 않도록 구현하였다.

---

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

int n, tri[501][501], memo[501][501];

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

int TopDown(int hereY, int hereX)
{
	if (hereX < 0 || hereX > hereY) return 0;
	if (hereY == 0) return tri[hereY][hereX];

	int& ret = memo[hereY][hereX];
	if (ret != -1) return ret;

	ret = 0;

	int val = tri[hereY][hereX];
	return ret = max(TopDown(hereY - 1, hereX - 1), TopDown(hereY - 1, hereX)) + val;
}

int BottomUp(int n)
{
	memo[0][0] = tri[0][0];

	for(int i = 1; i<n; i++)
		for (int j = 0; j < i + 1; j++)
		{
			int val = tri[i][j];
			if (j == 0)
				memo[i][j] = memo[i - 1][j] + val;
			else
				memo[i][j] = max(memo[i - 1][j - 1], memo[i - 1][j]) + val;
		}

	int res = -1;
	for (int i = 0; i < n; i++)
		res = max(res, memo[n - 1][i]);

	return res;
}

int main(void)
{
	memset(memo, -1, sizeof(memo));

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < i + 1; j++)
			cin >> tri[i][j];

	// Top-Down
	int res = -1;
	for (int i = 0; i < n; i++)
		res = max(res, TopDown(n - 1, i));
	cout << "TopDown: " << res << endl;
	
	// Bottom-Up
	cout << "BottomUp: " << BottomUp(n) << endl;

	return 0;
}

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