[SCPC] 11번: 개구리 뛰기

[SCPC] 11번: 개구리 뛰기

일직선 상에 돌들이 놓여있고, 개구리가 처음에는 '좌표 0'에 위치한 돌 위에 앉아 있다.

'좌표 0'에는 돌이 항상 놓여 있고, 모든 돌들은 정수 좌표에 놓여 있다. (그림 1)

개구리는 점프를 통해서 돌들 사이를 이동해서 마지막 돌까지 이동해야 한다. 이 때, 개구리가 한번의 점프로 이동 가능한 최대 거리 K가 주어진다. 개구리는 한번의 점프로 자신이 앉아 있던 돌에서 K 이하의 거리에 위치한 돌들 중 하나의 돌로 이동 할 수 있다. 여기서 문제는, '좌표 0'에 위치한 개구리가 마지막 돌까지 이동할 수 있다면, 마지막 돌까지 이동하기 위한 최소 점프 횟수를 계산하는 것이다.

예를 들어서, 위의 "그림1"의 예에서 보면, 한번의 점프로 이동 가능한 최대 거리가 K=4로 주어질 때, 아래 "그림2"에서와 같이 5회의 점프로 마지막 돌로 이동할 수 있고, 이것이 최소의 점프 횟수이다.

또한 위의 예에서, K=2로 주어진다면 개구리는 마지막 돌로 이동할 수가 없다. 왜냐하면, 개구리가 '좌표 2'의 돌로 이동한 후 '좌표 5'이상의 돌로는 이동할 수 없기 때문이다.

메모리 사용 제한

• heap, global, static (총계) : 256MB
• stack : 1MB

입력

입력 파일에는 여러 개의 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 T
가 주어지고, 이후 차례로 T개의 테스트 케이스가 주어진다. (1≤T≤5)
각각의 테스트 케이스 첫 번째 줄에는 '좌표 0'에 놓인 돌을 제외한 나머지 돌들의 개수 N이 주어진다. (1≤N≤1,000,000)

두 번째 줄에는 돌들이 놓인 좌표를 나타내는 N개의 정수 ai들이 빈칸(공백)을 사이에 두고 주어진다. (1≤ai≤10^9) 여기서, 주어진 좌표들은 증가하는 순서로 주어지고 모두 다르다.

세 번째 줄에는 개구리가 한 번의 점프로 이동 가능한 최대 거리 K가 주어진다. (1≤K≤10^9)

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에 “Case #T”를 출력하여야 한다. 이때 T는 테스트 케이스의 번호이다.

그 다음 줄에는 개구리가 마지막 돌로 이동할 수 있는 최소 점프 횟수를 출력한다. 만약, 개구리가 마지막 돌로 이동하는 것이 불가능한 경우에는 "-1"을 출력한다.

입출력예

입력

3
8
1 2 5 7 9 10 12 15
4
8
1 2 5 7 9 10 12 15
2
17
3 4 8 10 14 18 20 22 23 25 30 33 34 36 38 39 42
7

출력

Case #1
5
Case #2
-1
Case #3
8

출처

[SCPC 2015 - 1차 예선]

등록자

이프로

풀이

간단한 Greedy 알고리즘 문제입니다. 멀리 이동할수록 목적지에 더 적은 점프 횟수로 도달할 수 있기 때문에, 개구리는 최대한 멀리 이동하는 게 유리합니다. 따라서 개구리가 더이상 멀리 갈 수 없는 지점을 찾고, 개구리를 그 하나 이전 돌멩이로 이동시킵니다.

마지막 돌멩이는 비교할 지점이 없기 때문에 for문이 끝나면 이동 횟수에 +1 해줍니다. (보정)

인접한 두 돌의 거리가 최대 점프 거리를 넘어선 경우에는 이동이 불가능합니다. 이때 보정을 고려하여 값을 -2로 설정했습니다.

#include <vector>
#include <iostream>

using namespace std;

int Answer;

int main(int argc, char** argv) {
    int T; cin >> T;
    int num, jump, pos;
    vector<int> stones;

    for(auto test_case=0; test_case<T; test_case++)    {
    cin >> num;
    stones = vector<int>(num);
    for(auto i=0; i<num; i++) {
      cin >> stones[i];
    }
    cin >> jump;

    pos = 0; Answer = 0;
    for(auto i=1; i<stones.size(); i++) {
      if (stones[i] - stones[i-1] > jump) {
        Answer = -2;
        break;
      }
      if (stones[i] - pos > jump) {
        Answer++;
        pos = stones[i-1];
      }
    }
    Answer++;

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

    return 0;
}