개구리 점프

개구리 점프

SCPC 예선 1차

입출력

input

입력 파일에는 여러 개의 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 \(T\)가 주어지고, 이후 차례로 T개의 테스트 케이스가 주어진다. \(( 1≤T≤5 )\)

각각의 테스트 케이스 첫 번째 줄에는 ‘좌표 \(0\)‘에 놓인 돌을 제외한 나머지 돌들의 개수 \(N\) 이 주어진다. \(( 1≤N≤1,000,000 )\)

두 번째 줄에는 돌들이 놓인 좌표를 나타내는 \(N\) 개의 정수 \(a_i\)들이 빈칸(공백)을 사이에 두고 주어진다. \((1≤a_i≤10^9 )\)

여기서, 주어진 좌표들은 증가하는 순서로 주어지고 모두 다르다. 세 번째 줄에는 개구리가 한 번의 점프로 이동 가능한 최대 거리 \(K\) 가 주어진다. \(( 1≤K≤10^9 )\)

output

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에 “Case #T”를 출력하여야 한다. 이때 \(T\)는 테스트 케이스의 번호이다. 그 다음 줄에는 개구리가 마지막 돌로 이동할 수 있는 최소 점프 횟수를 출력한다. 만약, 개구리가 마지막 돌로 이동하는 것이 불가능한 경우에는 “-1”을 출력한다.

풀이 및 증명

접근법

위 문제는 탐욕법을 통해 쉽게 구현할 수 있으며 직관적이다.

처음에는 DP 알고리즘의 전개방식과 매우 흡사하여 DP로 구현하였지만 항상 정답에 포함되는 선택이 존재하여 탐욕 알고리즘으로 코드를 변경하였다.

증명

\(Claim\): \(K\)이하 길이에서 최대로 점프할 수 있다면 이는 항상 정답에 포함된다.

현재 위치에서 최대로 점프했을 때 ‘좌표 \(a\)‘이고 이는 정답에 포함되지 않는다고 가정하자. 그러면, 정답 ‘좌표 \(b\)’ 는 반드시 \((b < a)\)를 만족한다. 그리고 좌표 \(b\)에서 다음으로 진행할 최선의 수인 좌표 \(c\)가 존재할 것이다. \((c \le b + K)\)

하지만, \(b < a \to b + K < a + K\) 이므로 \(c < a + K\)이다. 즉, ‘좌료 \(a\)’ 를 선택해도 정답과 같은 경로를 구성할 수 있다. 따라서, ‘좌표 \(b\)’ 대신 ‘좌표 \(a\)‘로 점프하는 것도 정답에 포함되므로 가정은 모순이다.

\(\therefore\) \(K\)이하 길이에서 최대로 점프할 수 있다면 이는 항상 정답에 포함된다.

구현 및 코드

#include <iostream>
#include<algorithm>

using namespace std;

const int MAX_STONES_COUNT = 1.0e+6, MAX_VALUE = 1.0e+9;
int Answer, N, a[MAX_STONES_COUNT + 2], K, isjumpable;

int main(int argc, char** argv)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int T, test_case;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		//init
		Answer = 0;

		//input
		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> a[i];
		}
		cin >> K;

		//greedy
		for (int i = 0; i < N + 1;) {
			isjumpable = false;
			int jump = i;
			for (; a[jump + 1] - a[i] <= K && jump <= N; jump++) {
				//Go forward as much as possible if we can.
				isjumpable = true;
			}
			if (!isjumpable) {
				//If we can't move a single step, output -1.
				Answer = -1;
				break;
			}
			i = jump;
			Answer++;
		}

		//output
		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;
}

참고용 dp

#include<string.h>
#include <iostream>
#include<algorithm>

using namespace std;

const int MAX_STONES_COUNT = 1.0e+6, MAX = 1.0e+9;
int Answer, N, a[MAX_STONES_COUNT + 1], K, temp;
int cache[MAX_STONES_COUNT + 1];

int main(int argc, char** argv)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int T, test_case;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> a[i];
		}
		cache[N + 1] = 0;
		cin >> K;
		for (int i = N; i >= 0; i--) {
			int min_jump = MAX + 1;
			for (int jump = 1; a[i + jump] - a[i] <= K && i + jump <= N + 1; jump++) {
				min_jump = min(min_jump, cache[i + jump]);
			}
			cache[i] = min_jump + 1;
		}

		Answer = (cache[0] >= MAX + 1) ? -1 : cache[0];
		//output
		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;
}

위 코드는 최악의 경우 \(O(N^2)\)이므로 시간 제한에 걸렸었다.