Boj 2579 c++계단오르기

심심해서 몇문제 풀었다. 

이번 문제는 dp. 예전에 for문으로 한번 풀어보았기에 이번에는 재귀함수로 풀어보았다.

#include<iostream>
using namespace std;
int arr[301];
int dp[301];
int stair(int n){

    if(n==0){
        dp[0]=arr[0];
        return dp[0];
    }
    else if(n==1){
        dp[1]=arr[0]+arr[1];
        return dp[1];
    }
    else if(n==2){
        dp[2]= max(arr[0]+arr[2], arr[1]+arr[2]);//두 칸 중에서 더 큰 경우
        return dp[2];
}
    if(dp[n]!=0){
       return dp[n];
    }
    return dp[n]=max(stair(n-3)+arr[n-1]+arr[n], stair(n-2)+arr[n]);


}


int main(){

  int n;

  cin>>n;

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

핵심은 기억하며 더해주기. 이미 계산한 dp값에 대해서는 재귀연산을 하지 않는 것이다.