BOJ 22871 - 징검다리 건너기 (large)

문제

수열 \(A_N=A_1A_2\dots{A_i}\dots{A_N}\)에 대해 항 사이를 이동할 수 있다.
항상 오른쪽으로만 이동 가능하고, \(i\) 번째 항에서 \(j\) 번째 항으로 이동할 때 드는 비용은 \((j-i)\times{(1+|A_i-A_j|)},\quad i<j\)이다.
가장 왼쪽 항에서 가장 오른쪽 항으로 이동하는 임의의 경로에 대해 발생하는 비용들의 최댓값을 \(K\)라고 하면, \(K\)의 최솟값을 구하는 문제이다.

즉, 수열이 1 4 1 3 1로 주어진다면 1번째 - 3번째 - 5번째로 가는 경로가 드는 비용이 각각 2, 2로 최소 \(K\)가 된다.

풀이

dp[i] = i 번째 원소까지의 \(K\)의 최솟값이라 정의하면 아래와 같은 점화식이 나온다.
\(dp(i)=\text{min}(\text{max}(dp(j), \text{cost}(j\to{i})),\;\forall{j}<i)\)

소스코드

#include<iostream>
#include<vector>
#define abs(x) (x>0?x:-x)

using namespace std;
using vi=vector<int>;
using lld=long long;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	vi a(n, 0);
	vector<lld> dp(n, 5000000000);
	dp[0]=0;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			lld t=(lld)(i-j)*(1+abs((a[i]-a[j])));
			if(t<dp[j]) t=dp[j];
			if(dp[i]>t) dp[i]=t;
		}
	}
	cout<<dp[n-1];
	return 0;
}

풀고나서

• 정리하면서 supremum, infimum에 대해 복습했다.