알고스팟 알고리즘: 삼각형 위의 최대 경로(TRIANGLEPATH) [C++]

문제 출처: https://algospot.com/judge/problem/read/TRIANGLEPATH

algospot.com :: TRIANGLEPATH

1. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N;

int solution(vector <vector <int>> t, vector <vector <int>>& c, int x, int y)
{
	if (y == N - 1) return t[y][x];
	if (c[y][x] != 0) return c[y][x];
	int result = t[y][x] + max(solution(t, c, x, y + 1), solution(t, c, x + 1, y + 1));
	c[y][x] = result;
	return result;
}

int main(void)
{
	int C;
	cin >> C;

	while (C--)
	{
		cin >> N;

		vector <vector <int>> tri;
		vector <vector <int>> check(N, vector<int>(N, 0));

		for (int i = 0; i < N; i++)
		{
			vector <int> temp;
			for (int j = 0; j <= i; j++)
			{
				int input;
				cin >> input;
				temp.push_back(input);
			}
			tri.push_back(temp);
		}
		
		cout << solution(tri, check, 0, 0) << endl;
	}
}

(실행)

2. 풀이 방법

int solution(vector <vector <int>> t, vector <vector <int>>& c, int x, int y)
{
	if (y == N - 1) return t[y][x];    //삼각형 제일 밑에 도달했을 때
	if (c[y][x] != 0) return c[y][x];  //이미 확인했다면
	int result = t[y][x] + max(solution(t, c, x, y + 1), solution(t, c, x + 1, y + 1));
	c[y][x] = result;
	return result;
}

삼각형에서 아래와 오른쪽 아래로만 이동하기에 제일 밑에서 하루 위에 있는 위치에서는 경우의 수가 2가지이고 그 중에서 필요한 것은 가장 큰 값이기에 아래와 오른쪽 아래 중 가장 큰 값을 저장을 해두어서 계산의 횟수를 최소 시키면 이 문제를 해결할 수 있다.

3. 느낀 점

계산 결과를 저장한다는 생각을 못하고 이미 계산을 했지만 체크를 해서 이 문제가 오래 걸렸다. 다음에는 조금 더 빠르게 풀게 되었으면 한다.