백준 2579: 계단 오르기(DP)

계단: 2579

피보나치: 1003

그래서 동적계획법은 대체 머 어케하는건데??했던 지난날보다는 성장했지만

여전히 약간 꼬아놓은 문제는 간단하게 풀어내기 힘들다.

간단하게 풀었던 다른 문제들에 비해

(피보나치 함수는 내가 쉽게 풀었던 것에 비해 정답률이 생각보다 낮아서.. 너무 좋았따...크큭....)

계단문제에서 주춤했다. 사실 똑같이 간단한 문제인데... 정답에 접근하는 방법도 거의 근접했는데

어느 순간 생각이 산으로 가버리고...

#include <iostream>
 
#define max(a,b)            (((a) > (b)) ? (a) : (b))
 
int dp[301];
int stair[301];
 
int main()
{
    int N = 0;
    std::cin >> N;
    std::cin >> stair[1] >> stair[2];
    dp[1] = stair[1];
    dp[2] = stair[1] + stair[2];
    for (int i = 3; i <= N; ++i)
    {
        std::cin >> stair[i];
        dp[i] = max(dp[i - 2] + stair[i], dp[i - 3] + stair[i - 1] + stair[i]);
    }
    std::cout << dp[N];
    return 0;
}

코드를 짜면서도 '이렇게 풀면 될 것 같은데?' 하자마자

'음 아닌것같은데' (사실 정답이었다)

이건 개망한 접근방법

#include <iostream>
 
int dp[301];
 
int main()
{
    int N = 0;
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> dp[i];
    }
    int sum = 0;
    --N;
    int i = 2;
    while(N >= 0)
    {
        sum += dp[N];
        if (i == 2)
        {
            i = dp[N - 1] > dp[N - 2] ? 1 : 2;
        }
        else if (i == 1)
        {
            i = 2;
        }
        N -= i;
    }
    std::cout << sum;
    return 0;
}

개시발