문제 소개 📌

문제 링크 📢

https://www.acmicpc.net/problem/1932

문제 풀이 📝

구하는 것은 정수 삼각형에서 합이 최대가 되는 경로이다. 필자는 경로를 구성할 때 아래에서 위로 올라오면서 각 구간에서의 합의 최댓값을 갱신하는 방법을 사용했다.
한번 방문한 지점은 다시 갱신될 필요가 없기 때문에 dp에 값이 존재할 때는 해당 dp값을 반환해주고 재귀랑 dp를 사용해
dp[x][y] = max(triangle(x + 1, y), triangle(x + 1, y + 1)) + v[x][y];
와 같이 현재 지점을 갱신했다.
이와 같은 방식으로 아래에서부터 시작해 최상단까지 반복하여 합이 최대가되는 경로를 구할 수 있다!

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector <vector<int>> v;
vector <vector<int>> dp;
int N;
int triangle(int x, int y)
{
	if (x == N-1)
	{
		dp[x][y] = v[x][y];
		return v[x][y];
	}
	if (dp[x][y] == -1)
	{
		dp[x][y] = max(triangle(x + 1, y), triangle(x + 1, y + 1)) + v[x][y];
	}
	return dp[x][y];
}
int main()
{
	int num;
	vector <int> tmp1;
	vector <int> tmp2;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < i + 1; j++)
		{
			cin >> num;
			tmp1.push_back(num);
			tmp2.push_back(-1);
		}
		v.push_back(tmp1);
		dp.push_back(tmp2);
		tmp1.clear();
		tmp2.clear();
	}
	cout << triangle(0, 0);
	cout << dp[0][0];
	return 0;
}