[백준/BOJ] 백준 1932번 : 정수 삼각형

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

1932번: 정수 삼각형

(x, y) 위치부터 내려가는 경로 중 경로에 있는 수들의 합의 최대를 구하는 함수를 만든다. 경로를 찾을 때, 왼쪽 아래(x+1, y)로 내려가는 경우와 오른쪽 아래(x+1, y+1)로 내려가는 경로중 경로에 있는 수들의 합이 더 큰쪽을 선택한다

 

코드

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

int n;
int cache[500][500];
int triangle[500][500];


void makeCache()
{
	//-1로 초기화한다
	for (int i = 0; i < 500; i++)
		for (int j = 0; j < 500; j++)
			cache[i][j] = -1;
}

//(x,y)위치부터 내려가는 경로 중 경로에 있는 수들의 합의 최대를 구한다
int solve(int x, int y)
{
	//기저사례
	//삼각형의 끝 지점일때
	if (x == n - 1)
		return triangle[x][y];

	int& ret = cache[x][y];

	//이미 계산한적이 있을때
	if (ret != -1)
		return ret;

	//왼쪽아래와 오른쪽아래로 내로 내려가는 경로중, 경로에 있는 수들의 합이 더 큰쪽을 선택한다
	ret = max(triangle[x][y] + solve(x + 1, y), triangle[x][y] + solve(x + 1, y + 1));

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	//cache 초기화
	makeCache();

	int temp;
	
	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < i + 1; j++)
		{
			cin >> temp;
			triangle[i][j] = temp;
		}

	cout << solve(0, 0);

	return 0;
}