2016/01/31 코드그라운드 문제 SCPC2015 예선 : 개구리 뛰기

https://www.codeground.org/practice/practiceProbView.do?probId=11

생각해볼 점
1. dynamic 알고리즘 문제 -> P+1 번 째 돌까지 가려고 할 때 최소 점프횟수는 P,P-1,P-2,... 번 째 돌까지(뛸 수 있는 거리내에 있는 돌들)중에서의 최소 점프횟수 +1이다.

2. 좌표는 1billion까지 있지만 돌 갯수는 1million이 최대니까 배열은 돌 갯수에 맞춰서 만들면 된다.

3. 거리 확인을 위해 돌의 좌표를 저장한 배열을 따로 만들어야 한다. 문제에서 정렬된 순서로 돌 좌표를 준다고 했으니 따로 정렬을 할 필요는 없다.

4. c 자체에선 bool 개념이 없어서 typedef로 유사 개념을 만들어줘야 한다.
5. 컴퓨터 본체에서 돌렸는데도 stack overflow가 떴다. 1000000개 이상 배열은 heap으로 사용해야할 것 같다.
6. 답은 찾는데 시간제한 1초를 초과해서 만점을 못 받고 있다.

// 아래 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
#include <stdio.h>
#include <stdlib.h>
typedef enum {false,true} bool;
int main(void) {
    /* 아래 freopen 함수는 input.txt를 read only 형식으로 열고, 표준입력(키보드) 대신 input.txt 로 부터 읽어오겠다는 의미의 코드입니다.
    만약 본인 PC 에서 테스트 할 때는, 입력값을 input.txt에 저장한 후 freopen 함수를 사용하면
       그 아래에서 scanf 함수를 사용하여 표준입력 대신 input.txt 파일로 부터 입력값을 읽어 올 수 있습니다.
       또한, 본인 PC에서 freopen 함수를 사용하지 않고 표준입력을 사용하여 테스트하셔도 무방합니다.
    단, Codeground 시스템에서 "제출하기" 할 때에는 반드시 freopen 함수를 지우거나 주석(//) 처리 하셔야만 합니다. */
 // freopen("input.txt", "r", stdin);
 setbuf(stdout, NULL);
 int TC;
 int test_case;
 int N, i,K,p,minHopPoint,minHop;
 bool first;
 int* arr = (int*)malloc(1000001 * sizeof(*arr));
 int* hop = (int*)malloc(1000001 * sizeof(*hop));
 scanf("%d", &TC);
 for (test_case = 1; test_case <= TC; test_case++) {
// 이 부분에서 알고리즘 프로그램을 작성하십시오. 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
  scanf("%d", &N);
  arr[0] = 0, hop[0] = 0;
  for (i = 1; i <= N; i++) {
   scanf("%d", &arr[i]);
  }
  scanf("%d", &K);
  for (i = 1; i <= N; i++) {
   p = i - 1;
   minHopPoint = -1;
   minHop = -1;
   first = true;
   while (arr[i] - arr[p] <= K && p >= 0) {
    if (first) {
     first = false;
     minHop = hop[p];
     minHopPoint = p;
    }
    else if (minHop > hop[p]) {
     minHop = hop[p];
     minHopPoint = p;
    }
    p--;
   }
   if (minHopPoint < 0) hop[N] = -1,break;

   else hop[i] = hop[minHopPoint] + 1;
  }
  // 이 부분에서 정답을 출력하십시오.
  printf("Case #%d\n", test_case);
  printf("%d\n", hop[N]);
 }
 return 0; // 정상종료 시 반드시 0을 리턴해야 합니다.
}