🙇‍♀️[Silver I] 정수 삼각형 - 1932

문제 링크

성능 요약

메모리: 4796 KB, 시간: 16 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 1월 4일 23:57:10

문제 설명

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

🚀풀이

DP문제로 삼각형의 맨위부터 시작해서 그대로 내려갈건지 오른쪽 아래로 내려갈건지 두가지의 경우가 존재한다.

각 경우에 대해서 최대값을 저장하는 배열을 만들고 계속 내려간다.

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

int path(int y, int 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;
	}

	// 적용
	//ret = cache[y][x];
	//ret += max(ret, cache[y + 1][x]);
	//ret += max(ret, cache[y + 1][x + 1]);

	return ret = board[y][x] + max(path(y + 1, x), path(y + 1, x + 1));
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;


// 오늘의 주제 : TrianglePath
// - (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)
		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;
	}

	// 적용
	//ret = cache[y][x];
	//ret += max(ret, cache[y + 1][x]);
	//ret += max(ret, cache[y + 1][x + 1]);

	return ret = board[y][x] + max(path(y + 1, x), path(y + 1, x + 1));
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);
	cin >> N;

	board = vector<vector<int>>(N + 1);
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			int temp;
			cin >> temp;
			board[i].push_back(temp);
		}
	}

	//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 << '\n';

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

	//while (y < N)
	//{
	//	if (y == N - 1)
	//	{
	//		cout << board[y][x];
	//		break;
	//	}
	//	cout << board[y][x] << " -> ";

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

참고