징검다리 건너기 (large)

백준 22871번: 징검다리 건너기 (large)

아이디어

cur->next로 가는 비용을 구할 때 cur->i로 가는 비용, i->next로 가는 비용중 더 큰 값을 취하고, 이렇게 취한 값중 가장 작은 값을 구한다.

코드

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int MAX = 5001;
int N, arr[MAX], cache[MAX][MAX];

int solve(int cur, int next) {
    if (cur == N) return 0;

    int& ret = cache[cur][next];
    if (ret != -1) return ret;

    ret = LLONG_MAX;
    for (int i = cur+1; i < N+1; i++) {
        int nc = (i-cur)*(1+abs(arr[i]-arr[cur]));
        ret = min(ret, max(nc, solve(i, next)));
    }
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i < N+1; i++) {
        cin >> arr[i];
    }
    memset(cache, -1, sizeof(cache));

    cout << solve(1, N);

    return 0;
}

여담

int 범위를 벗어나니 조심.