[종만북 문제] 삼각형 위의 최대 경로 수 세기 (문제 ID : TRIPATHCNT, 난이도 : 중)

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

---

핵심 :

1. 간단한 DP 문제지만.. 재귀로도 풀어보자.

---

[종만북 문제] 삼각형 위의 최대 경로 수 세기 (문제 ID : TRIPATHCNT, 난이도 : 중)

이번 문제도, 간단하게 DP 로 풀 수 있다. 예를 들어 다음과 같다.

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

using namespace std;

/****************************************************************************************************/

int N;
vector<vector<pair<int, int>>> cache;

int arr[100][100];

void sol()
{
	cache[0][0] = make_pair(arr[0][0], 1);

	for (int i = 1; i < N; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			if (j == 0)
			{
				cache[i][j] = make_pair(cache[i-1][j].first + arr[i][j], 1);
			}
			else if (j == i)
			{
				cache[i][j] = make_pair(cache[i - 1][j - 1].first + arr[i][j], cache[i - 1][j - 1].second);
			}
			else
			{
				int leftVal = cache[i-1][j-1].first;
				int leftCnt = cache[i-1][j-1].second;

				int upVal = cache[i-1][j].first;
				int upCnt = cache[i-1][j].second;

				if (leftVal == upVal)
				{
					cache[i][j] = make_pair(leftVal + arr[i][j], leftCnt + upCnt);
				}
				else if (leftVal > upVal)
				{
					cache[i][j] = make_pair(leftVal + arr[i][j], leftCnt);
				}
				else
				{
					cache[i][j] = make_pair(upVal + arr[i][j], upCnt);
				}
			}
		}
	}

	int maxVal = 0;
	int maxCnt = 0;
	for (int j = 0; j < N; ++j)
	{
		if (maxVal < cache[N - 1][j].first)
		{
			maxVal = cache[N - 1][j].first;
			maxCnt = cache[N - 1][j].second;
		}
		else if (maxVal == cache[N - 1][j].first)
		{
			maxVal = cache[N - 1][j].first;
			maxCnt += cache[N - 1][j].second;
		}
	}

	cout << maxCnt << endl;
}

void inputHandler()
{
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			cin >> arr[i][j];
		}
	}

	cache.resize(N, vector<pair<int, int>>(N, {0, 0}));
}

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

		sol();
	}

	return 0;
}

 

코드가 조금 장황해졌는데... 책에서는 아래와 같이 점화식을 세우고,

깔끔하게 재귀함수로 구현했다.

int countCache[100][100];

// (y, x) 에서 시작해서 맨 아래줄까지 내려가는 경로 중 최대 경로의 개수 반환
int count(int y, int x)
{
	// 기저 사례 : 맨 아래줄에 도달
	if (y == N-1)
		return 1;

	// 메모이제이션
	int& ret = countCache[y][x];
	if (ret != -1)
		return ret;
	ret = 0;
	if (path2(y+1, x+1) >= path2(y+1, x))
		ret += count(y+1, x+1);
	if (path2(y+1, x+1) <= path2(y+1, x))
		ret += count(y+1, x);
	return ret;
}

참고로 path2 함수는 아래처럼 생겼다. 자세한 내용은 이 글 참고.

// (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];
}