문제 설명

백준 2579번 계단 오르기

전체적인 문제 설명은 위에 링크에서 확인하고 중요한 조건들만 확인 해보겠다.

1. 계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟을 수 없다.
3. 마지막 도착 계단은 반드시 밟아야한다.
4. 시작할때 첫번째 계단부터 밟을 필요는 없다. 두번째 계단부터 밟을 수도 있다.
5. 계단을 밟으면 쓰여진 점수 얻게 된다. 얻을 수 있는 점수의 최대값을 구해야한다.

입력

첫번째는 계단의 수, 두번째 줄은 계단의 쓰여진 점수가 주어진다.

제한 조건

제한 조건으로는 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10000이하의 자연수이다.

풀이 내용

이번 문제는 재귀로 구현 하였다. dp는 도착 계단에서 부터 첫번째 계단으로 내려가며 구현 하였고
재귀가 끝날때마다 최대값을 memo배열에 저장하도록 했다.

dp를 들여다 보면 4가지의 조건이 있다.

1. if (n==0) 재귀가 마지막 바닥에 닿았을때, 재귀의 끝을 알려 주는 조건이다.
   n == 0 이므로 맨 처음 밟은 계단이며 첫번째 계단의 점수를 반환 한다.

2. if (n < 0) n < 0 이전 계단에서 2칸을 건너 뛰어 첫번째 계단을 밟지 못했을때 이다. 0을 리턴하여 최댓값에 영향을 주지 않도록 구현 했다.

3. if (memoValue != -1) 동적 프로그래밍의 핵심이다. 이미 지금까지의 계단을 내려올때 최대값을 저장해두었기 때문에 값이 존재 할 경우 바로 저장한 값을 리턴한다.

4. if (count == 1) 연속된 계단을 두번 밟았을 때이다. 이 경우에는 다음 계단을 무조건 두칸 뛰어넘게 구현 하였다.
   아닐 경우는 한칸 내려간 경우와 두칸 내려간 경우를 모두 구하여 최대값을 선택하였다.

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int arr[300];
int memo[300][2];

long long dp(int n, int count){
    int &memoValue = memo[n][count];

    if (n == 0)
        return arr[n];

    if (n < 0)
        return 0;

    if (memoValue != -1){
        return memoValue;
    }

    long long ret;
    if (count == 1){
        ret = dp(n-2, 0);
    }else{
        ret = max(dp(n-1, count+1), dp(n-2, 0));
    }

    memoValue = ret + arr[n];
    return memoValue;
}

int main(){
    int n;
    cin >> n;
    memset(memo, -1 ,sizeof(memo));

    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }

    cout << dp(n-1, 0);
}