[C++ 자/알 Note] TRIANGLE PATH 문제

TLIANGLE PATH 문제 

(0,0)부터 시작해서 아래 or 아래우측으로 이동 가능하다
이동한 경로의 숫자를 모두 더한 값이

최대가 되는 경로와 합을 출력하시오

 

구현 주의사항

- 동적계획법 코드 템플릿

동적계획법을 이용한 코드 작성 시에

"기저사항 -> 캐시확인 -> 연산" 방식으로 작성하면 편하다

 

- 함수 반환 타입

문제가 원하는 최대가 되는 합

즉, 지금까지의 합을 반환하도록 구현하면 된다

참고로, 재귀함수 특성 상 위에서 부터 합이 추가되는 것이 아닌

끝에서부터 추가 되는 방식이다 (추후 확인 가능)

 

- 기저사항

N을 삼각형의 높이라고 가정하고

y좌표와 x좌표로 이동을 하는 경우에

높이 N-1을 초과하는 y좌표의 이동은 불가능하다

그렇기에 

y좌표가 N-1이 되면, 자신의 값을 반환하면서 종료해야 한다

혹은 y좌표가 N이 되면, 0을 반환하면서 종료하도록 구현하면 된다

 

- 캐시확인

갈 수 있는 모든 경로들로 재귀함수가 호출되면서

가장 최대값의 경로 및 합만 저장이 될 것이다

특히,

특정 위치에 달하는 최대값의 경로 및 합은 고정적이며 반복적으로 호출된다

따라서, 해당 결과들을 캐시에 저장해 memoization을 이용하면 된다

참고로 참조타입 임시 변수를 이용해 cache 값을 받아서

해당 임시변수를 활용하고 저장하는 방식이 추천된다

 

- 연산

현재 기준 다음으로 갈 수 있는 두 가지 길을

재귀적으로 호출하도록 구현하면 된다

그리고 a와 b 중에 큰 값을 반환하는 max 함수를 이용해서

아래 or 아래우측 중 가장 큰 값만 활용하고 반환하면 된다

 

- 경로는?

현 위치에서 다음으로 가야 하는 next 위치를 저장할

2차원 벡터를 만들어야 한다

그리고 아래 or 아래우측 중 어떤 길이 더 큰 값을 반환하는지

비교해서 next 위치를 저장해 주면 된다

 

코드 구현

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

int path(int y, int x)
{
	// 기저 사항
	// 1번 방식
	// if (y == N - 1)
	//	return board[y][x];
	
	// 2번 방식
	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;
	}

	// 연산
	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++;
	}

}