문제
고속도로에서 자동차를 타고 Lkm 떨어진 목적지로 이동하려고 한다. 출발지에서 자동차의 기름 탱크에는 기름이 가득 차 있다. 하지만 자동차의 기름 탱크의 크기가 충분히 크지 않기 때문에, 고속도로 가운데의 N개의 휴게소들 중 몇 개에 들러 주유를 해야 한다. 목적지에 다다르기 위한 최소 주유 횟수를 계산하는 프로그램을 작성하시오.
입력
첫 줄에는 휴게소의 수 N과 기름 탱크의 크기 M, 출발지에서 목적지까지의 거리 L이 주어진다. (1≤N≤1,000, 1≤M<L≤1,000,000,000) 기름 탱크 크기 M은 이 자동차가 주유를 받지 않고 이동할 수 있는 거리가 최대 M km까지임을 의미한다.
그 다음 N개의 줄에는 각각의 휴게소의 위치 정보가 주어진다. 한 줄에는 한 개의 휴게소의 위치를 나타내는 한 개의 수 Xi(0<Xi<L)가 주어진다. 이것은 출발지로부터 Xi km 떨어진 휴게소가 존재함을 의미한다. 휴게소는 위치 순서대로(출발지에서 가까운 것부터 차례대로) 주어진다. 같은 위치에 두 개 이상의 휴게소가 존재하는 경우는 입력으로 주어지지 않는다.
목적지에 도착하는 것이 불가능한 경우는 입력으로 주어지지 않는다.
출력
목적지까지 도착하기 위한 최소 주유 횟수를 하나의 정수로 출력한다.
힌트
입력 예제
5 30 100
30
40
50
60
70
출력 예제
3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <iostream> #include <queue> #include <algorithm> #include <limits.h> //RestArea ------------------- void fileInput(); void RestArea(); //RestArea ------------------- int main( int argc, char ** argv) { RestArea(); return 0; } //RestArea ------------------- //휴게소 개수, 기름탱크크기(최대 갈수 있는 거리), 내가 가야할 거리 int N, M, L; //(1≤N≤1,000, 1≤M<L≤1,000,000,000 int X[1001]; //휴게소 위치 int D[1001]; void fileInput(){ scanf ( "%d %d %d" , &N, &M, &L); for ( int i=1;i<=N;i++){ scanf ( "%d" , &X[i]); } } void RestArea(){ X[0] = 0; D[0] = 0; fileInput(); int count = 0; for ( int i=1; i<=N; i++){ int min = INT_MAX; for ( int j=i-1; j>=0; j--){ if (X[i] - X[j] <= M){ //한번에 갈 수 있는 거리 if (min > D[j]){ min = D[j]; } } else { break ; } } D[i] = min + 1; if (X[i] + M >= L){ count = D[i]; break ; } } printf ( "%d" , count); } //RestArea ------------------- |