[22871] 징검다리 건너기

 

 

이분탐색 문제다.

 

가장 왼쪽 돌에서 가장 오른쪽 돌로 건너갈 수 있는 모든 경우의 수 중에서 K의 최솟값을 구하는 문제다. K는 i 에서 j 번째 돌로 이동할 때 걸리는 힘이며, (j - i) * (1 + |Ai - Aj|)로 구할 수 있다.

 

K의 범위는 1부터( j - i = 1 & Ai == Aj ) 최대( j - i = N - 1 & Ai와 Aj가 최대, 최소)일 경우이며 이 범위는 순차적이다. 따라서  K값으로 징검다리를 건널 수 있는지 확인하면서 건널 수 없는 경우 K를 늘려주고, 아니라면 K를 줄여주는 방법으로 K를 이분탐색할 수 있다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int N;

	cin >> N;
	int rock[5001];

	int max_rock = 0;
	int min_rock = INT_MAX;

	for (int i = 0; i < N; i++) {
		cin >> rock[i];

		if (max_rock < rock[i]) max_rock = rock[i];
		if (min_rock > rock[i]) min_rock = rock[i];
	}

	int start = 1;
	int end = (N - 1) * (1 + max_rock - min_rock);

	while (start <= end) {
		int middle = (start + end) / 2;

		int dp[5001] = { 0 };
		for(int i = 0; i < N; i++)
			for (int j = 0; j < i; j++) {
				if (dp[i] == 1) break;

				if (dp[j] != 0) {
					int k = (j - i) * (1 + abs(rock[i] - rock[j]));

					if (middle >= k)
						dp[i] = 1;
				}
			}

		if (dp[N - 1] == 1) end = middle - 1;
		else start = middle + 1;
	}

	cout << end;
}