백준 22871, 징검다리 건너기

개요

문제 링크
실버 1, DP

끝점까지 이동하는 모든 경로마다 필요한 비용의 최솟값 구하기

---

접근

1. dp를 사용한다. 들어갈 값은 i번째 까지 갈 때 필요한 비용의 최솟값
2. 갱신하는 경우는 자신보다 앞에 있는 값에 대해 max(앞에 저장된 값, 새로 구한 값)이 더 작은 경우
3. 왜 max(앞에 저장된 값, 새로 구한 값)이냐? 경로를 대표하는 값 = 경로에 필요한 비용의 최대 이고, 우리는 이 대푯값의 최솟값을 구해야 하므로
4. 즉 dp[i] = 경로의 대푯값의 최솟값이고 더 작은 경로를 찾는 경우 갱신한다.
   주의할 점 : integer * integer이므로 integer overflow 가능

---

Pseudo code

dp[i] = min_value_till_i
새로 구한 값 = (i-j)*(1+abs(a[i]-a[j]))
경로의 대푯값 = max(dp[previous], 새로 구한 값)
if (경로의 대푯값 < dp[i])
    dp[i] = (새로운) 경로의 대푯값

---

Source code

#include <bits/stdc++.h>
using namespace std;

using ld = long long;
int main() {
    int n;
    cin >> n;
    int a[n+1];
    ld dp[n+1];
    for (int i=1; i<=n; i++)
        cin >> a[i];
    dp[1] = 0;
    for (ld i=2; i<=n; i++) {
        dp[i] = 5e9;
        for (ld j=1; j<i; j++) {
            ld v = (i-j)*(1+abs(a[i]-a[j]));
            dp[i] = min(dp[i], max(dp[j],v));
        }
    }
    cout << dp[n];
}