본문 바로가기

개발/알고리즘

휴게소

문제


고속도로에서 자동차를 타고 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 -------------------




'개발 > 알고리즘' 카테고리의 다른 글

중앙값  (0) 2016.12.03
보드 게임  (0) 2016.12.03
술 약속  (0) 2016.12.03
보석  (0) 2016.12.03
풍선  (0) 2016.12.02