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

 
#include <iostream>
#include <queue>
#include <tuple>
 
int stair[301] = {};
int DP[301] = {};
 
int main()
{
    int N = 0;
    std::cin >> N;
 
    int iCount = 0;
    stair[0] = 0;
 
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> stair[i];
    }
 
    DP[1] = stair[1]; 
    DP[2] = std::max(stair[2], stair[1] + stair[2]);
    DP[3] = std::max(stair[1] + stair[3], stair[2] + stair[3]);
 
    for (auto i = 4; i <= N; ++i)
    {
        DP[i] = std::max(stair[i] + DP[i - 2], stair[i] + stair[i - 1] + DP[i - 3]);
    }
 
    std::cout << DP[N];
 
    return 0;
}

이번 코테에서 DP문제에 고배를 써서 DP문제를 많이 풀어봐야겠다고 생각해서 풀었다.

que로 했더니 메모리 초과.. 

최대 두칸이고, 그 뒤로는 두칸 위로 올라가야하는건데...

접근하는 방법을 생각하는 게 어려웠다.

어떤 한 칸에 들어가는 방법이

 

2칸 전(DP) + (점프 후)올라왔을 때의 칸,

3칸 전(DP) + (점프 후)1칸 전 + 올라왔을 때의 칸 

 

이렇게 두 방법을 비교해서 풀어야 했다.