[C++] 백준 2579번 : 계단 오르기

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

2579번: 계단 오르기

 

 

 

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    int v[301],tmp[301]={0};

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    
    tmp[0]=v[0];
    tmp[1]=max(v[1]+v[0],v[1]);
    tmp[2]=max(v[2]+v[1],v[2]+v[0]);
    for(int i=3;i<n;i++){
        tmp[i]=max((tmp[i-2]+v[i]),(tmp[i-3]+v[i-1]+v[i]));
    }
    cout<<tmp[n-1];

    return 0;
}

DP

=> 각 계단에서의 최대값을 구한다. 

 

 

첫번째 칸[0]: 무조건 v[0]

두번째 칸[1]: v[0]을 밟고 v[1]을 밟는 경우 / v[0]을 밟지 않고 v[1] 밟는경우 비교

 

세번째칸부터 최종적으로 밟을 칸 : 

1. 목적칸[n]을 밟기전에 [n-1] 칸을 밟을 경우 -> 무조건 [n-3]칸을 밟아야함

2. 목적칸[n]을 밟기전에 [n-2] 칸을 밟을 경우 

 

두 가지 경우의 max값을 구해나간다.