[백준/BOJ] 백준 2579번 : 계단 오르기

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

2579번: 계단 오르기

현재 계단의 위치(number)와, 지금까지 연속으로 밟은 계단(seq)으로 지금 한번에 1계단을 오르는 게 좋을지, 한번에 2계단을 오르는 게 좋을지 선택한다.

 

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int cache[301][3];
int n;
vector<int> stair;

//연속으로 밟은 계단이 seq개 일때, number번째(0번째는 시작점)계단부터 오르는 경우 총 점수의 최댓값 구하기
int solve(int number, int seq)
{
	//계단의 마지막 지점 일때
	if (number == n)
		return stair[n];

	//계단의 마지막 지점을 넘었을때는 포함되지 않으므로 매우 작은 수를 반환한다
	if (number > n)
	{
		return -987654321;
	}

	int& ret = cache[number][seq];

	//ret가 -1이 아니면 계산했던것이다
	if (ret != -1)
		return ret;

	//연속으로 2계단을 밟았을때 다음은 무조건 한번에 2계단을 올라야 한다(연속으로 3개의 계단을 밟을 수 없으므로)
	if (seq == 2)
	{
		ret = stair[number] + solve(number + 2, 1);
		return ret;
	}
	
	//처음에 한번에 1계단을 오르고 그 이후를 고려하는 경우와 한번에 2계단을 오르고 그 이후를 고려하는 경우중 큰 수가 최댓값이다
	ret = max(stair[number] + solve(number + 1, seq + 1), stair[number] + solve(number + 2, 1));
	return ret;
}

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

	//cache를 -1로 초기화 한다
	memset(cache, -1, sizeof(cache));


	int result;
	int temp;

	cin >> n;

	//stair[0]은 시작점으로, 시작점의 점수는 0점이다
	stair.push_back(0);

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		stair.push_back(temp);
	}

	result = solve(0, 0);

	cout << result << "\n";

	return 0;
}