[codeground] Practice. 11. 개구리 뛰기

  문제   

일직선 상에 돌들이 놓여있고, 개구리가 처음에는 '좌표 0'에 위치한 돌 위에 앉아 있다.
'좌표 0'에는 돌이 항상 놓여 있고, 모든 돌들은 정수 좌표에 놓여 있다. (그림 1)

[ 그림 1 ]

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

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

 

[ 그림 2 ]

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

 

 

  입력   

입력 파일에는 여러 개의 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 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"을 출력한다.

 

 

 

 

 

 

 

아... 20, 40, 80, 100 아주 다양한 점수를 받았다. 에휴ㅠㅠ

 

자....그라믄...

 

 나의 풀이 

우선 배열로 하면 방 개수때문에 세그먼트 오류가 발생한다. 그래서 vector를 이용해준다.

 

그리고 개구리의 시작 위치는 입력받는 값이 아닌 0부터 시작이라는 것을 주의하자!

 

 

#include <iostream>
#include <vector>
using namespace std;

int Answer;

int main()
{
	int T, test_case;
	int n, k, point, cnt;  //point = 개구리의 위치를 가짐, cnt 한번에 뛰는 거리를 가짐
	vector<int> arr;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++) {

		Answer = 0;
		point = 0;

		cin >> n;
		arr.assign(n+1, 0); //첫번째 방에는 0이 있어야하기때문에 n+1만큼 생성 
		for (int i = 1; i <= n; i++)
			cin >> arr[i];
		cin >> k;

		if (n != 1)
			while (point < n) {
				cnt = 1; //한칸 앞부터 비교 시작을 위해 1로 초기화
				while (1) {
					if (arr[point + cnt] - arr[point] > k) break;
                    //cnt만큼 옮겼을 때 k보다 많이 갔으면 그만 돌린다.
					cnt++;
					if (cnt+point>n) break;
                    //개구리가 n보다 더 가지 않게 막는다.
				}
				cnt--; //1부터 시작했기때문에 하나 빼준다.
				if (cnt) { //개구리가 돌 하나라도 갈 수 있다면 개구리를 옮겨준다.
					Answer++;
					point += cnt;
				}
				else { //개구리가 돌 하나라도 못간다면 멈춘다.
					Answer = -1;
					break;
				}
			}

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

	return 0;
}