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

www.acmicpc.net/problem/2579

2579번: 계단 오르기

0층부터 올라가는 구조로 탑다운으로 풀고있었는데 풀면서 느꼈다.

문제 조건상 무조건 마지막 계단을 밟아야되는데

이렇게 마지막이 확정된 경우라면 마지막계단 우선 밟고 내려가는 구조로 바텀업방식 알고리즘이 무조건 쉬울거라고..

 

 

근데 일단 오기가 생겼고 탑다운도 가능할거라 생각해서 탑다운으로도 풀었다(오래걸렸다)

 

확실히 바텀업이 코드도짧고 직관적임

 

 

 

탑다운풀이

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int arr[303];
int dp[303][3];
 
int stair(int x, int cnt) {
 
    if (x == n) return arr[n];
    //목적지를 넘어서면 아주 큰 음수를 줘서 답이 못 되게 
    if (x == n + 1) return -100000000;
 
    int& ret = dp[x][cnt];
    if (ret != -1) return ret;
 
 
    //한번에 연속된 3칸은 밟을 수 없음    
    if (cnt == 2) return ret = arr[x] + stair(x + 2, 1);
    return ret = arr[x] + max(stair(x + 1, cnt + 1), stair(x + 2, 1));
 
}
int main() {
 
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    memset(dp, -1, sizeof(dp));
    cout << stair(0, 0);
 
    return 0;
}

 

 

바텀업

애초에 반복문 조건이 n까지이기 때문에

마지막 계단을 안 밟고 n을 넘어서는걸 생각할 필요가 없다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int arr[303];
int dp[303][3];
 
int main() {
 
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    for (int i = 1; i <= n; i++) {
        dp[i][1] = arr[i] + max(dp[i - 2][1], dp[i - 2][2]);
        dp[i][2] = arr[i] + dp[i - 1][1];
    }
    cout <<max(dp[n][1], dp[n][2]);
    
 
    return 0;
}