[백준] 2579번 계단 오르기

문제 링크

 

풀이

계단을 연속해서 세 계단을 오를 수 없고 연속해서 두 번 혹은 한 계단을 건너뛸 수 있습니다. n번째 계단은 반드시 밟아야 합니다. 즉 n-3, n-2, n 순서대로 밟거나 n-3, n-1, n의 두 가지 경우를 점화식으로 도출할 수 있습니다. 이 중에서 큰 값을 구하면 되는 것이죠. 앞의 순서는 d[n-2] + s[n]이며 뒤는 d[n-3] + s[n-1] + s[n]입니다.

 

코드

#include <cstdio>
#include <algorithm>
int main()
{
	int N;
	scanf("%d", &N);
	int s[301] = { 0 };
	int d[301] = { 0 };
	for (int i = 1; i <= N; ++i)
		scanf("%d", &s[i]);
	d[1] = s[1];
	d[2] = s[1] + s[2];
	d[3] = s[3] + std::max(s[1], s[2]);
	for (int i = 4; i <= N; ++i)
		d[i] = std::max(d[i - 3] + s[i - 1], d[i - 2]) + s[i];
	printf("%d", d[N]);
}