[해커랭크] Truck Tour (C++)

문제 링크: www.hackerrank.com/challenges/truck-tour/problem

Truck Tour | HackerRank

1. 주의할 점

- 기름과 거리는 1:1 비율이다

 

2. 구현

- 파라미터로 넘겨받은 자료를 통해 각 지점에서 다음 지점까지 사용되는 자원?을 구한다. 자원은 (해당 지역에서 충전할 수 있는 기름 양 - 다음 정류장까지의 거리)로 구한다 -> 1:1 비율이므로

- 위의 값들은 Cost[] 배열에 담는다

- For문 * While문을 통해 현재 자원의 값을 Sum에 저장하며, 처음위치에 도달할때까지 Sum이 음수가 아니라면 한 바퀴 도는 작업이 가능하기 때문에 시작점을 출력한다

 

long long cost[100001];
 
int truckTour(vector<vector<int>> petrolpumps) {
    /*
     * Write your code here.
     */
    int num = petrolpumps.size();
    int result;
    for(int i=0;i<num;i++)
        cost[i] = petrolpumps[i][0] - petrolpumps[i][1];
    long long sum;
    for(int i=0;i<num;i++){
        sum=cost[i];
        if(sum<0) continue;
        int idx = (i+1)%num;
        bool avail=true;
        while(idx!=i){
            sum+=cost[idx];
            if(sum<0){
                avail=false;
                break;
            }
            idx = (idx+1)%num;
        }
        if(avail){
            result = i;
            break;
        }
    }
    return result;
}