2579 계단오르기

딱 봐도 dp문제~~

 

로직은 바로 생각나서 구현했는데 허점이 좀 있었다. 

 

허점1 

시작할 때 한 칸 또는 두 칸 뛸 수 있다 - 문제 잘 읽자

허점2

상태 저장을 안 했다 - 이전에 한 칸으로 뛰어 왔는지 두 칸으로 뛰어 왔는지 저장이 따로 안 됐다. 

-> dp는 인자로 들어온 값(상태)를 모두 저장해야 한다.

그래서 dp[3005][5]로 상태도 저장하게 바꿨다.

허점3

마지막 칸에 도달하지 않는 경우 0으로 처리를 했었다. 0이면 작은 값이라 선택되지 않을거라 생각했는데 아니었다... 

이런 경우를 대비해서 엄청 작은 음수를 사용했다. 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int n;
int v[305];
// 상태를 저장하는 배열 [index][한 칸 뛰었는지 / 두 칸 뛰었는지]
int dp[305][5];

int func(int idx, int len) {
// 정확히 n-1이 아니면 엄청 작은 수 리턴 (절대 답이 되지 않게끔)
    if (idx >= n)
        return -1000000000;
    
// 마지막 칸일 경우
    if (idx == n - 1)
        return v[idx];

// 이미 있는 값인 경우
    if (dp[idx][len] != 0)
        return dp[idx][len];
    
// 초기값 설정
    int a = -1000000000, b = -1000000000;
    // 이전에 두 칸으로 온 경우에만 한 칸 뛰기 가능
    if (len == 1)
        a = func(idx + 1, len + 1);
    b = func(idx + 2, 1);
    
    return dp[idx][len] = max(a, b) + v[idx];
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
    // 시작시 첫번째 칸으로 갈지, 두 번째 칸으로 갈지 경우를 나눔
    printf("%d\n", max(func(0, 1), func(1, 1)));

    return 0;
}