[알고스팟] 삼각형 위의 최대 경로 (최적 부분 구조)

링크: https://www.algospot.com/judge/problem/read/TRIANGLEPATH

algospot.com :: TRIANGLEPATH

---

 동적 계획법이란 완전탐색 알고리즘에서 중복되는 부분문제를 메모이제이션으로 해결하는 것을 의미합니다. 동적 계획법 알고리즘을 계획할 때는 몇 가지 중요한 조건이 있는데, 하나는 참조 투명성이며 다른 하나는 최적 부분 구조(optimal substructure)입니다.

 최적 부분 구조란 부분문제의 최적화가 전체 문제의 최적화로 이어지는 구조를 의미합니다. 예를 들어 서울-부산 최적의 경로를 구하고자 할 때 서울-대전, 대전-부산으로 문제가 나뉘어질 수 있다고 합시다. 서울-대전의 경로를 최적화했을 때 결과적으로 항상 전체 경로가 최적화된다면 이를 최적 부분 구조가 성립한다고 이야기합니다.

 이를 이용하여 문제를 풀어봅시다. 문제의 점화식은 다음과 같습니다.

$$MaximumSum(x, y) = triangle[x][y] + max(MaximumSum(x + 1, y), MaximumSum(x, y + 1))$$

위에서부터 삼각형을 타고 내려가며 숫자를 더한다고 했을 때, 현재 행의 최대합은 이전까지의 최대합에 현재 행에서 가능한 경우의 수를 더합니다. 이는 직관적으로 최적 부분 구조입니다. 따라서 이전에 도달한 위치의 최대합을 계산해놓는다면 동적 계획법으로 쉽게 문제를 해결할 수 있습니다.

<파이썬3 소스코드>

import sys
rl = lambda: sys.stdin.readline()

def get_maximum_path(depth, idx):
    now = tri[depth][idx]
    if depth == len(tri) - 1:
        return now
    if cache[depth][idx] > 0:
        return cache[depth][idx]
    
    cache[depth][idx] = now + max(
        get_maximum_path(depth + 1, idx), 
        get_maximum_path(depth + 1, idx + 1)
    )
    return cache[depth][idx]

for _ in range(int(rl())):
    tri = []
    cache = []
    for _ in range(int(rl())):
        row = list(map(int, rl().split()))
        tri.append(row)
        cache.append([0 for _ in range(len(row))])

    print(get_maximum_path(0, 0))

 

<C++ 소스코드>

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>


int getMaximumPath(const int depth, const int idx,
	const std::vector<std::vector<int>>& triangle,
	std::vector<std::vector<int>>& cache)
{
	int now = triangle[depth][idx];
	size_t length = triangle.size();
	int cachedValue = cache[depth][idx];

	if (cachedValue > 0) return cachedValue;
	if (depth == length - 1) return now;

	cache[depth][idx] = now + std::max<int>(getMaximumPath(depth + 1, idx, triangle, cache), getMaximumPath(depth + 1, idx + 1, triangle, cache));
	return cache[depth][idx];
 }

int main(void)
{
	int numTestcase;
	scanf("%d", &numTestcase);

	for (int t = 0; t < numTestcase; t++)
	{
		int length;
		scanf("%d", &length);
		std::vector<std::vector<int>> triangle;
		std::vector<std::vector<int>> cache;

		for (int i = 0; i < length; i++)
		{
			triangle.push_back(std::vector<int>());
			cache.push_back(std::vector<int>());
			for (int j = 0; j <= i; j++)
			{
				int elem;
				scanf("%d", &elem);
				triangle[i].push_back(elem);
				cache[i].push_back(0);
			}
		}
		printf("%d\n", getMaximumPath(0, 0, triangle, cache));
	}
	

	return 0;
}