[종만북 문제] 삼각형 위의 최대 경로 (문제 ID : TRIANGLEPATH, 난이도 : 하)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 평범한 DP 문제로, for-loop 혹은 재귀함수로 풀 수 있다.

---

[종만북 문제] 삼각형 위의 최대 경로 (문제 ID : TRIANGLEPATH, 난이도 : 하)

일단 for-loop 으로 푼 버전을 보자.

#include <iostream>
#include "stdlib.h"
#include <vector>
#include <cmath>

using namespace std;

int N;
int tri[100][100];
int cache[100][100];

void sol()
{
	cache[0][0] = tri[0][0];

	for (int i = 1; i < N; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			if (j == 0)
				cache[i][j] = cache[i - 1][j] + tri[i][j];
			else
				cache[i][j] = max(cache[i - 1][j - 1], cache[i - 1][j]) + tri[i][j];
		}
	}
	
	int maxVal = 0;
	for (int j = 0; j < N; ++j)
		maxVal = max(maxVal, cache[N - 1][j]);
	cout << maxVal << endl;
}

void inputHandler()
{
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
	 		cin >> tri[i][j];
			cache[i][j] = 0;
		}
	}
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		sol();
	}

	return 0;
}

 

책에는 아래처럼 점화식으로 푸는 버전을 소개한다.

// (y, x) 위치부터 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로의 합을 반환
int path2(int y, int x)
{
	// 기저 사례
	if (y == N - 1)
		return tri[y][x];
	
	// 메모이제이션
	int& ret = cache[y][x];
	if (ret != 0)
		return ret;
	return ret = max(path2(y + 1, x), path2(y + 1, x + 1)) + tri[y][x];
}