개구리 뛰기
2017-02-07 13:42:49 | 조회수 1736
개구리는 0번에서 시작하고, N번이 도착 지점이며, 개구리가 한 번에 뛸 수 있는 거리는 K이다.
이 때, 개구리가 N번에 도착하기 위해 뛰어야 하는 횟수의 최솟값을 구하는 문제이다.
간단한 1차원 DP 문제로, 현재 위치에서 뛸 수 있는 지점에 현재 위치까지 도달하는데 뛴 횟수 + 1과, 기존에 도착한 경우가 있다면 그 횟수와 비교하여 더 작은 값을 저장한다. 예를 들어, 2번에 도달할 수 있는 경우는 0→1→2 (2번) 또는 0→2 (1번) 이 있는데, 이 경우는 1을 저장한다. 이런방식으로 끝까지 모두 비교한 후 정답을 출력해주면 된다.
클릭하여 소스코드 보기
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
using namespace std;
static int road[1000000] = { 0 };
int main()
{
int t;
cin >> t;
for (int i = 1; i <= t; i++)
{
int n, k, p = 0, idx = 0, ans = 1;
bool f = true;
cin >> n;
for (int j = 0; j < n; j++)cin >> road[j];
cin >> k;
for (int j = 0; j < n; j++)
{
if (road[j] - p > k)
{
if (j - idx == 1)
{
cout << "Case #" << i << "\n-1\n";
f = !f;
break;
}
idx = j - 1;
p = road[j - 1];
ans++;
j--;
}
}
if(f)
cout << "Case #" << i << "\n" << ans << "\n";
}
}