백준 2579번 계단 오르기

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

처음 생각한 알고리즘과 코드

처음에 밟는 계단이 너무 복잡해서
밟지 않는 계단을 생각해냈다.

밟지 않는 계단은 1칸 떨어져있거나 2칸 떨어져있으므로
n번째 계단은 무조건 밟지 않는다는 가정 하에
n개의 밟지 않는 계단의 최소점수합은 n-2번째와 n-3번째 중 적은 점수합과 n번째 계단의 점수합일거라 생각했다.

#include <stdio.h>

int main()
{
	int minus[303];//밟지 않는 계단의 점수 합을 이 배열에 저장할 것
	int i, n, total;
	scanf("%d", &n);
	total = 0;
	for (i = 0; i < 3; i++)
	{
		minus[i] = 0; //if문을 쓰지 않고 일반화하기 위해 일단 처음 세개는 값을 0으로 주었다.
	}
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &minus[i + 2]);
		total += minus[i + 2];//여가서 total은 모든 계단의 점수 합
		minus[i + 2] += minus[i] < minus[i - 1] ? minus[i] : minus[i - 1];
	}
	total -= minus[n] < minus[n + 1] ? minus[n] : minus[n + 1];//minus는 minus[n+2]까지 저장되나 n+2번째 칸은 밟아야하므로 생각할 필요X, 마지막칸 전과 전전 중 하나는 밟지 말아야 하므로(둘다 밟으면 마지막 칸을 밟을수 없다.) 둘 중 하나를 비교하여 더 작은 것이 최소한의 점수로 계단을 밟지 않는 것이다. 
	printf("%d", total);
}

두번째 알고리즘

이건 밟는 계단의 점수합의 최대를 직접 구하는 방식이다.

n번째 계단의 경우 n-1번째 또는 n-2번째 계단을 밟아야 하므로 그 두개의 점수합 최대 중 하나를 선택해 n번째 계단의 점수와 더하면 될 것 같지만
사실 그래선 안 되는게 n - 1번째 계단의 경우 그걸 밟게 되면 n - 2번째 계단을 밟았을 때는 제외해야 한다.
즉, n-3번째 계단까지의 합과 n-1번째 계단의 숫자의 합 또는 n-2번째 계단까지의 합 중 더 큰 걸 골라야 한다.

#include <stdio.h>

int main()
{
	int stair[303];
	int total[303];
	int i, N;
	scanf("%d", &N);
	for (i = 0; i < 3; i++)
	{
		total[i] = 0;
		stair[i] = 0;// 1,2,3번째 계단에서 문제가 없도록 0으로 설정
        이러면 첫번째 계단의 경우 무조건 0이 더해지므로 자기 자신
        두번째 계단의 경우 0이 더해지거나 1번째 계단과의 합이므로 1번째 계단과의 합
        세번째 계단의 경우 첫번째 계단과의 합 또는 0번째까지의 합과 두번째 계단의 합 즉, 두번째 계단과의 합이므로 둘중 더 큰 걸 고르게 된다.
	}
	for (i = 3; i < N + 3; i++)
	{
		scanf("%d", &stair[i]);
		total[i] = stair[i];
	}
	for (i = 0; i < N; i++)
	{
		total[i + 3] += total[i + 1] > total[i] + stair[i + 2] ? total[i + 1] : total[i] + stair[i + 2];
	}
	printf("%d", total[N + 2]);
	return 0;
}