[Codeground 11번] 개구리 뛰기

문제 출처 :

https://www.codeground.org/practice/practiceProblemList

알고리즘 분석 :

문제 해결에 필요한 사항

1. Greedy Algorithm

2. 구현

이 문제는 개구리가 점프해서 도착지점까지 최소의 횟수로 가야한다.

개구리가 점프 할 수 있는 범위가 주어지기에 greedy로 해결 할 수 있다.

즉 가장 멀리 점프 할 수 있는곳부터 계속 찾아가면 결국 최솟값으로 도착 할 수 있다는 것이다.

알고리즘을 어느정도 접하였다면 이 문제를 bfs 또는 dp로 한번쯤 생각해 볼 수도 있지만, 탐욕으로 충분히 문제가 풀리고,

bfs는 수의 범위가 크기에 TLE, DP로도 해당 점프 구간이 커지면 TLE가 날 것이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int arr[1000002];
 
int main()
{
    int tCase;
    scanf("%d", &tCase);
    for (int tc = 1; tc <= tCase; tc++)
    {        
        int n;
        scanf("%d", &n);
 
        int last;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &arr[i]);
            last = arr[i];
        }
        int jump;
        scanf("%d", &jump);
 
        int i = 0;
        int cnt = 0;
        while (1)
        {
            int here = arr[i];
            int herePos = i;
            
            // 가능한 점프 구간까지 계속 점프            
            while (arr[i] - here <= jump && i <= n)
                i++;
 
            i--; 
 
            if (here == last) // 도착했다면
            {
                printf("Case #%d\n%d\n", tc, cnt);
                break;
            }
            else if (i == herePos) // 점프를 못했다면
            {
                printf("Case #%d\n-1\n", tc);
                break;
            }
            cnt++;
        }
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>