백준 2579번 계단 오르기

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

프로그래밍 대회에서 배우는 알고리즘 문제해결전략에서 익힌대로 재귀함수를 이용하여 풀고 싶었지만 아직 부족해서 그런지 재귀함수를 사용하지 못했습니다.

/*

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다

계단 오르는 데는 다음과 같은 규칙이 있다.

1.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2.연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.

3.마지막 도착 계단은 반드시 밟아야 한다.

 

도착 후 최대값을 반환하는 프로그램을 작성하시오

*/

#include <iostream>

#include <algorithm>

using namespace std;

 

int cache[300];

int stair[300]; //계단 최대 300개

int stairCnt; //계단 갯수

 

//이 문제는 재귀로 작성하지 못했습니다...

int maxSum(void)

{

        cache[0] = stair[0];

        cache[1] = stair[0] + stair[1]; //계단에 쓰여있는 점수는 자연수이므로 stair[1]보다 stair[0]+stair[1]이 무조건 크다

        cache[2] = max(stair[0] + stair[2], stair[1] + stair[2]); //1칸+2칸 vs 2칸+1칸

 

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

               cache[i] = max(cache[i - 2] + stair[i], stair[i - 1] + stair[i] + cache[i - 3]); //2칸을 올라갈 경우 vs 1칸씩 두번 올라갈 경우(연속해서 3칸을 올라가면 안되므로 cache[i-3] 추가)

        return cache[stairCnt - 1];

}

 

int main(void)

{

        cin >> stairCnt;

 

        for (int i = 0; i < stairCnt; i++)

               cin >> stair[i];

        cout << maxSum() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~