[백준]Baekjoon2579(Dynamic Programming)

문제링크 : https://www.acmicpc.net/problem/2579

동적계획법으로 풀면 어렵지 않게 풀 수 있는 문제이다.

먼저 각 계단의 점수를 저장하기 위해 stair[301]을 선언하였고

계단을 올라갈 때 마다 최대 점수를 저장하기 위해 score[301][3]을 선언하였다.

여기서 score[i][0]은 그 전 계단을 밟고 i 번째 것을 안밟는 경우.

          score[i][1]은 그 전 계단을 밟지 않고 i번째 것을 밟는 경우.

          score[i][2]는 그 전 계단을 밟고 i번째 계단도 밟는 경우이다.

#include <iostream>
#include <algorithm>

using namespace std;

long long score[301][3];
int stair[301];
int main()
{
	int n; //계단의 수
	scanf("%d", &n);
	for (int i = n; i >= 1; i--) scanf("%d", &stair[i]);
	score[2][0] = stair[1];
	score[2][1] = 0;
	score[2][2] = stair[1] + stair[2];
	score[1][0] = stair[1]; score[1][1] = 0; score[1][2] = stair[1];

	for (int i = 3; i <= n; i++) {
		score[i][0] = max(score[i - 1][1], score[i - 1][2]);
		score[i][1] = score[i - 1][0] + stair[i];
		score[i][2] = score[i - 1][1] + stair[i];
	}
	printf("%lld", max(max(score[n][0], score[n][1]), score[n][2]));
	

}