백준 2579 - 계단 오르기

각 계단에는 점수가 있습니다.
연속된 세 계단 밟을 수 없고, 한번에 한개 혹은 두개 계단만 올라갈 수 있고, 마지막 계단은 반드시 밟아야 한다는 조건에서 밟은 계단의 최대 점수를 구하는 문제입니다.

다이나믹 프로그래밍(Divide & Conquer와 같은 말인 줄 이제 알았습니다)을 이용해 해결할 수 있는 문제입니다.

마지막 계단은 무조건 밟아야 하므로 마지막 계단에서의 최대점수를 그림으로 보면 다음과 같이 나옵니다.
이전 발판을 밟는다면 그 이전 발판은 밟을 수 없습니다. 그렇다면 이 때의 최대 점수는 3번째 전 발판에서의 최대 점수에 이전 발판의 점수와 현재 발판의 점수를 더한 값이 됩니다.
이전 발판을 밟지 않고 두번째 이전 발판을 밟는다면 해당 발판에서의 최대 값에 현재 발판을 더한 값이 최대값이 됩니다.

이를 반복해서 모든 발판에서의 최대값을 구할 수 있습니다. 단, 첫번째 발판과 두번째 발판은 그 이전 발판을 계산할 수 없으므로 직접 값을 넣어줘야 합니다.

#include <iostream>
#include <vector>

int main()
{
	int cnt;
	std::cin >> cnt;

	std::vector<int> stairs(1, 0);
	for (int i = 0; i < cnt; i++)
	{
		int stair;
		std::cin >> stair;
		stairs.push_back(stair);
	}

	std::vector<int> scores(stairs.size());

	scores[0] = 0;
	scores[1] = stairs[1];
	scores[2] = stairs[1] + stairs[2];

	for (int i = 3; i < scores.size(); i++)
	{
		scores[i] = std::max(scores[i - 3] + stairs[i - 1] + stairs[i], scores[i - 2] + stairs[i]);
	}

	std::cout << scores[scores.size() - 1];

	return 0;
}