[DP] Chapter 03. 샘플 문제 : TRIANGLE_PATH

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/f3e8c575947be7453c8520077b7b38702a954ee0

TRIANGLE_PATH · developeSHG/Data_Structure-Algorithm@f3e8c57

 

 

---

 

 

TRIANGLE_PATH
- (0,0)부터 시작해서 아래 or 아래우측으로 이동 가능
- 만나는 숫자를 모두 더함
- 더한 숫자가 최대가 되는 경로? 합?

 

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
#include <thread>
#include <windows.h>

// 오늘의 주제 : 동적 계획법 (DP)
// TRIANGLE_PATH
// - (0,0)부터 시작해서 아래 or 아래우측으로 이동 가능
// - 만나는 숫자를 모두 더함
// - 더한 숫자가 최대가 되는 경로? 합?

// 6
// 1 2
// 3 7 4
// 9 4 1 7
// 2 7 5 9 4

int N;
vector<vector<int>> board;
vector<vector<int>> cache;
vector<vector<int>> nextX;

int path(int y, int x)
{
	// 기저 사항
	//if (y == N - 1)
	//	return board[y][x];
	if (y == N)
		return 0;

	// 캐시 확인
	int& ret = cache[y][x];
	if (ret != -1)
		return ret;

	// 경로 기록
	{
		int nextBottom = path(y + 1, x);
		int nextBottomRight = path(y + 1, x + 1);
		if (nextBottom > nextBottomRight)
			nextX[y][x] = x;
		else
			nextX[y][x] = x + 1;
	}

	// 적용
	// board[y][x] + path(y + 1, x); // 아래로 갈 경우
	// board[y][x] + path(y + 1, x + 1) // 대각선 어래로 갈경우
	return ret = board[y][x] + max(path(y + 1, x), path(y + 1, x + 1));
}

int main()
{
	board = vector<vector<int>>
	{
		{6},
		{1, 2},
		{3, 7, 4},
		{9, 4, 1, 7},
		{2, 7, 5, 9, 4}
	};

	N = board.size();
	cache = vector<vector<int>>(N, vector<int>(N, -1));
	nextX = vector<vector<int>>(N, vector<int>(N));

	int ret = path(0, 0);
	cout << ret << endl;

	// 경로 만들기
	int y = 0;
	int x = 0;

	while (y < N)
	{
		cout << board[y][x] << " -> ";

		x = nextX[y][x];
		y++;
	}
}