백준(BOJ) 2579번 계단 오르기

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

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

코드 ( C ++ )

#include <iostream>

#include <algorithm>

using namespace std;

int stairs[301];

int cache[301];

int N;

void find()

{

cache[0] = 0;

cache[1] = stairs[1];

cache[2] = stairs[1] + stairs[2];

for (int i = 3; i <= N; ++i)

 // 3번 연속해서 오를수는 없다.  전 단계에서 두칸을 뛰는 경우와, 세칸 전에서 두칸뛰고 한칸뛰는 경우로 나뉜다.

cache[i] = max(cache[i - 2] + stairs[i], cache[i - 3] + stairs[i] + stairs[i - 1]);

}

int main()

{

cin >> N;

for (int i = 1; i <= N; ++i)

{

cin >> stairs[i];

}

find();

cout << cache[N] << endl;

return 0;

}