개구리 뛰기


작성일 : 2017-02-07 13:42:49
조회수 : 782


본문


개구리는 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";
    }
}

개구리 뛰기 - 알고리즘닷컴
여기서는 https://codeground.org 풀이를 포스팅합니다.

3 개의 글