[BOJ 22871, C++] 징검다리 건너기(large)

https://www.acmicpc.net/problem/22871

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

 

풀이

항상 오른쪽으로만 갈 수 있다고 했으므로 바로 DP문제라는 것을 알 수 있습니다.

돌로 건너갈 수 있는 모든 경우 중 K의 최솟값을 구하라고 했으므로 왼쪽 -> 오른쪽으로 가는 동안 쓰는 힘의 최대값들중에서 최솟값을 출력하면 됩니다.

 

코드

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
 
const int N = 5001;
int n;
ll arr[N], dp[N];
 
ll go(int x) {
    if (x == n - 1) return 0;
    ll& ret = dp[x];
    if (ret != -1) return ret;
 
    ret = 1e10;
    for (int i = x + 1; i < n; i++) {
        ret = min(ret, max(go(i), (i - x) * (1 + abs(arr[x] - arr[i]))));
    }
    return ret;
}
 
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    cout << go(0) << endl;
 
    return 0;
}