[BOJ 22869, C++] 징검다리 건너기 (small)

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

22869번: 징검다리 건너기 (small)

 

풀이

항상 오른쪽으로 이동한다는 내용을 통해 DP문제임을 알 수 있습니다.

왼쪽에서 오른쪽으로 갈 수 있는지 여부를 확인한다는 것은 힘을 K이하로 쓰고 건널 수 있냐는 뜻이므로 왼쪽에서 오른쪽으로 가는동안 필요한 힘의 최댓값을 구하고, 이 힘들중에서 최솟값을 구하여 K이하이면 YES, K 초과이면 NO를 출력하면 됩니다.

 

 

코드

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
 
const int N = 5001;
int n, k;
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 >> k;
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    if (go(0) <= k) cout << "YES" << endl;
    else cout << "NO" << endl;
 
    return 0;
}