[코드 그라운드] 11번 : 개구리 뛰기 [SCPC 예선 문제] [미해결]

문제

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

 

[ 그림 1 ]

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

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

 

[ 그림 2 ]

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



- 제한시간 : 전체 테스트 케이스는 5개 이하이며, 전체 수행 시간은 1초 이내 (Java 2초 이내) 
    제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
    그때까지 수행한 결과에서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 됩니다.
    그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
    이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
    C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
    제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.                                     ※ 언어별 기본 제공 소스코드 내용 참고
    만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.

- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB
- 제출 제한 : 최대 10회 (제출 횟수를 반영하여 순위 결정 → 동점자의 경우 제출 횟수가 적은 사람에게 높은 순위 부여)
- 제출 제한 : 최대 7회

메모리 사용 제한

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

입력

입력 파일에는 여러 개의 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 TT가 주어지고,
이후 차례로 TT개의 테스트 케이스가 주어진다. ( 1≤T≤51≤T≤5 ) 
각각의 테스트 케이스 첫 번째 줄에는 '좌표 0'에 놓인 돌을 제외한 나머지 돌들의 개수 NN 이 주어진다. ( 1≤N≤1,000,0001≤N≤1,000,000 )
두 번째 줄에는 돌들이 놓인 좌표를 나타내는 NN 개의 정수 aiai들이 빈칸(공백)을 사이에 두고 주어진다. (1≤ai≤1091≤ai≤109 )
여기서, 주어진 좌표들은 증가하는 순서로 주어지고 모두 다르다.
세 번째 줄에는 개구리가 한 번의 점프로 이동 가능한 최대 거리 KK 가 주어진다. ( 1≤K≤1091≤K≤109 )

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에 “Case #T”를 출력하여야 한다.
이때 TT는 테스트 케이스의 번호이다.
그 다음 줄에는 개구리가 마지막 돌로 이동할 수 있는 최소 점프 횟수를 출력한다.
만약, 개구리가 마지막 돌로 이동하는 것이 불가능한 경우에는 "-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 363 38 39 42 7

출력

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

푸는 TIP

나같은 경우는 배열 입력을 받았을 때, arr[0]에 배열의 크기를 저장하고, 데이터들을 arr에 저장해준다. -> 배열이 포인터로 데이터를 옮기기 때문에 데이터의 크기가 얼마나 되는지 알 수 없다.(sizeof로) 따라서 따로 arr[0]에 size를 저장해준다.

그리고 jump로 저장된 최대 점프로 해보고, 만약 배열에 동일한 데이터가 없는 경우 -1인 상태로 데이터 있는지 확인한다. 이를 반복해서 확인해보고 가장 멀리 점프하도록 유도한다. 기능을 분리해야함으로 새로운 함수를 작성해서 적용한다.

소스 코드

#include <stdio.h>
#include <malloc.h>
int Answer;
int move(int * arr, int jump);
int checking(int* arr, int input);
int* insert_data(int* arr);
int can_Across(int * arr, int jump);

int main(void)
{
	int T, test_case;
	int* arr = NULL;
	int jump = 0;
	setbuf(stdout, NULL);
	scanf("%d", &T);

	for (test_case = 0; test_case < T; test_case++)
	{
		Answer = 0;
		arr = insert_data(arr);
		scanf("%d", &jump);
		if (can_Across(arr, jump) == 0) {
			Answer = -1;
		}
		else {
			Answer = move(arr, jump);
		}
		printf("Case #%d\n", test_case + 1);
		printf("%d\n", Answer);
		free(arr);
	}
	return 0;
}

int move(int * arr, int jump) {
	int moved = 0;
	int count = 0;
	int size = arr[0];
	int toMove=0;
	while(moved < arr[size]) {
		toMove=jump+1; //밑에 while문을 do while로 고치기 싫어서 사용 
		while(toMove--){
			if(checking(arr, moved+toMove)){
				moved = moved+toMove;
				count++;
				break;
			}
			else{
				continue;
			}
		}
	}
	return count;
}

int checking(int* arr, int input) {
	int size = arr[0];
	int i=1;
	for(i=1;i<=size;i++){
		if(input == arr[i]){
			return 1;
		}
	}
	return 0;
}
int* insert_data(int* arr) { //arr의 index 0에는 data의 개수를 저장 
	int size;
	scanf("%d",&size);
	arr = (int *)malloc(sizeof(int) * (size+1));
	int i=1;
	for (i = 1; i <= size; i++) {
		scanf("%d", &arr[i]);
	}
	arr[0] = size;
	return arr;
}

int can_Across(int * arr, int jump) {
	int size = arr[0];
	int i = 1;
	for (i = 1; i < size; i++) { //data 개수-1까지 확인하면 종료 
		if (arr[i + 1] - arr[i] > jump){
			return 0;
		}
		else {
			continue;
		}
	}
	return 1;
}

느낀 점

test case들은 모두 통과했지만 time out이 뜬 걸로 봐서 시간 복잡도가 매우 높은걸로 예상된다. 아마 moving 함수에서 for문 2개에다가 checking함수의 for문까지 하나, 총 3개의 for문과 1개의 함수를 이동하는 것 때문에 시간 복잡도가 O(N^3)이상으로 커진 것 같다. 다른 방법을 찾아봐야겠다.

출처

[SCPC 2015 - 1차 예선]