소스 코드

#include <iostream>
#include <algorithm>
#define endl "\n"
#define MAX_N 300
using namespace std;

int n;// 계단 개수
int scores[MAX_N + 1]; // 계단의 점수
int d[MAX_N + 1]; // 최대 점수

void input()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> scores[i];
	}
}

void solve()
{
	d[1] = scores[1];
	d[2] = scores[1] + scores[2];
	for (int i = 3; i <= n; ++i)
	{
		d[i] = max(d[i - 2] + scores[i], d[i - 3] + scores[i - 1] + scores[i]);
	}

	cout << d[n] << endl;
}

int main()
{
	//freopen("boj_2579.txt", "r", stdin);

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	input();
	solve();

	return 0;
}

해설

규칙에 맞춰서 계단을 올랐을 때 얻을 수 있는 점수 중 최대값을 구하는 문제. 백트래킹으로 풀이 시 시간 복잡도가 지수승이므로 시간 초과 발생. 시간 복잡도를 줄이기 위해 다이나믹 프로그래밍(bottom-up)으로 풀이.

해당 문제에서 주의해야할 조건은 3계단을 연속해서 오르지 못하는 것이므로, (두번째 전 계단의 최대값 + 현재 계단의 점수)와 (세번째 전 계단의 최대값 + 첫번째 전 계단의 점수 + 현재 계단의 점수)를 비교하여 더 큰 값을 현재 계단의 dp 테이블에 저장해야 함.