계단 오르기

1. 재귀형 완전 탐색

#include <iostream>
#include <vector>

using namespace std;

vector< vector<int> > tri;
int N;

int step (int value, int row, int col)
{
	// 자기가 있는 곳까지의 값의 합을 가지고 시작한다.
	
	// 기저 사례
	// 여기가 끝일 경우 -> 현재까지의 값을 리턴.
	if (row == N-1) return value; 
	
	// 재귀 사례
	// 바로 밑으로 가거나 오른쪽 밑 중에서 큰 값을 리턴한다.
	return max(step(value+tri[row+1][col], row+1, col),
			   step(value+tri[row+1][col+1], row+1, col+1));
}

int main ()
{
	int hi;
	cin >> N; // size of triangle

	tri.assign(N, vector<int>(N, 0)); // NOT (N*N, 0)
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= i; j++)
			cin >> tri[i][j];
	}
	
	hi = step(tri[0][0], 0, 0);
	
	cout << hi << endl;
	
}

2. 메모이제이션 적용

#include <iostream>
#include <vector>

using namespace std;

vector< vector<int> > tri;
vector< vector<int> > cache;
int N;

// 자기가 있는 곳까지의 값의 합을 가지고 시작한다.
int step (int value, int row, int col)
{
	// 메모이제이션
	// 만약 이전에 한번 와봤던 곳이고
	// 예전의 합보다 지금 합이 더 작으면
	// 더 나아가는 것이 의미가 없으므로 더 이상 실행하지 않는다.
	if (cache[row][col] != -1 && cache[row][col] > value) return 0; 
	// 아니라면 현재값을 저장한다.
	else cache[row][col] = value;
	
	// 기저 사례
	// 여기가 끝일 경우 -> 현재까지의 값을 리턴.
	if (row == N-1) return value; 
	
	// 재귀 사례
	// 바로 밑으로 가거나 오른쪽 밑 중에서 큰 값을 리턴한다.
	return max(step(value+tri[row+1][col], row+1, col),
			   step(value+tri[row+1][col+1], row+1, col+1));
}

int main ()
{
	int hi;
	cin >> N; // size of triangle

	tri.assign(N, vector<int>(N, 0)); // NOT (N*N, 0)
	cache.assign(N, vector<int>(N, -1));
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= i; j++)
			cin >> tri[i][j];
	}
	
	hi = step(tri[0][0], 0, 0);
	
	cout << hi << endl;
	
}

3. 비교식 제거

#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

vector< vector<int> > tri;
vector< vector<int> > cache;
int N, hi=-1;

// 자기가 있는 곳까지의 값의 합을 가지고 시작한다.
void step (int value, int row, int col)
{
	// 기저 사례
	// 여기가 끝일 경우 -> 더이상 나아가지 않는다.
	if (row == N-1) {
		// hi(최댓값)를 지속적으로 업데이트한다.
		if (hi < value) hi = value;
		return;
	}
	
	// 재귀 사례
	// 메모이제이션
	// 이전에 와봤을 경우보다 큰 경우에만 나아간다.
	if (cache[row+1][col] < value+tri[row+1][col])
	{
		cache[row+1][col] = value+tri[row+1][col];
		step(value+tri[row+1][col], row+1, col);
	}
	if (cache[row+1][col+1] < value+tri[row+1][col+1])
	{
		cache[row+1][col+1] = value+tri[row+1][col+1];
		step(value+tri[row+1][col+1], row+1, col+1);
	}
}

int main ()
{
	scanf("%d", &N); // size of triangle

	tri.assign(N, vector<int>(N, 0)); // NOT (N*N, 0)
	cache.assign(N, vector<int>(N, -1));
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= i; j++)
			scanf("%d", &tri[i][j]); 
	}
	
	step(tri[0][0], 0, 0);
	
	cout << hi << endl;
	
}