codeground 개구리 뛰기

[ 해결 방법 ]

점프를 할 수 있는 범위에서 제일 큰 돌의 좌표를 고르면 된다. 예를 들어 4칸을 뛸 수 있고 현재 위치는 첫번재 돌에 있다. 그리고 돌이 1, 2, 5, 7.. 순으로 있다면, 점프해서 최대로 갈 수 있는 위치는 4이지만 4에 돌이 없으므로 가장 가까운 2로가야한다. 다음엔 2에서 6까지 뛸 수 있지만 6에 돌이 없으므로 가장 가까운 5로간다.

[ 코드 ]

#include <stdio.h>
#define INF	2000000000
int T, tmpT;
int pos[1000002];
int main()
{
	scanf("%d", &T);
	tmpT = T;
	while (tmpT--)
	{
		int N, K;
		int pre, cur = 0, next, jmp = 0;
		scanf("%d", &N);
		for (int i = 1; i <= N; i++)
			scanf("%d", pos + i);
		pos[N + 1] = INF;
		scanf("%d", &K);
		
		while (cur < N)
		{
			next = pos[cur] + K;
			pre = cur;
			while (pos[cur] <= next)
				cur++;
			cur--;
			if (pre == cur)
			{
				jmp = -1; break;
			}
			jmp++;
			//printf("pos[%d] = %d, jmp = %d\n", cur, pos[cur], jmp);
		}
		printf("Case #%d\n", T - tmpT);
		printf("%d\n", jmp);
	}
	return 0;
}