[C] 백준 2579번 (계단 오르기)

각 계단을 밟을 때마다 얻을 수 있는 점수가 주어지고, 한 번에 한 칸 또는 두 칸만 움직여서 가장 높은 점수를 얻어 그 값을 출력하는 문제다. 단, 연속되는 계단 3개를 전부 밟는 것은 안 된다.

n번째 계단까지 올랐을 때 얻을 수 있는 최고점수를 f(n)이라 하고,
n번째 계단이 가지고 있는 점수를 score(n) 이라고 하면, 
다음과 같은 식을 생각해 볼 수 있다. f(n) = score(n) + max( f(n-1),  f(n-2) )

f(n-1)보다 f(n-2)의 값이 더 크다면 다행이지만 만약, f(n-1)의 값이 더 크고 그 값이 n-2번째 계단과 n-1번째 계단을 밟아서 만들어진 값이라면 문제가 생긴다.
이 경우에 f(n-1)에 score(n)을 더하면 (n-2) , (n-1) , n 세 개의 연속되는 계단을 모두 밟은게 되어버린다.

그렇다면 이걸 어떻게 처리해야 할까? 한 칸 오르는걸 1, 두 칸 오르는 걸 2라고 표현한다면
f(n)의 값이 만들어지는 과정의 마지막은 2 또는 2, 1인 경우만 가능하다.
2, 1, 1로 오르는 것은 불가능하다. 현재 밟고 있는 계단 + 그 다음 것 + 그 다음 것 3개를 연속해서 밟는것이 된다.
마지막에 2칸 오르는 것은 1이 중복될 리가 없으니 신경쓸 게 없다. 
하지만, 마지막에 1칸을 오르는 것은 그 직전에 또 1이 있었는지 아닌지를 반드시 확인해줘야한다.
n-1번째 계단에서 1칸 올라서 n번째 계단으로 가려고하는 상황의 이전 단계에서 2칸을 오르게끔 만들어야하는 것이다.
(n-1)에서 n으로 가기 전 상황을 2칸 오르는 상황으로 만들려면 (n-3)에서 (n-1)로 가는 상황이 되도록 해줘야 한다.

따라서 우리는 위 공식에서 f(n-1)이 아니라 대신 f(n-3) + score(n-1)을 넣어주어야 한다.
f(n) = score(n) + max( f(n-3) + score(n-1),  f(n-2) ) 최종적으로 이런 공식을 얻을 수 있고, 이걸 이용해 코드를 작성하자.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int max(a, b) {
	int result = a;
	if (b > a) result = b;
	return result;
}

int f[301];

int main(void) {	
	int n; scanf("%d", &n); 
	int score[301];
	for (int i = 1; i <= n; i++) {
		scanf("%d", &score[i]);
	}
	
	f[1] = score[1];
	f[2] = score[1] + score[2];
	
	for (int i = 3; i <= n; i++) {
		f[i] = score[i] + max(f[i - 3] + score[i - 1], f[i - 2]);
	}
	printf("%d", f[n]);
}