휴게소 시작 지점 고르기 알고리즘

고속도로 순환 알고리즘

 

Q.

어느 도시에 원형으로 된 도로가 존재한다.

도로에는 N개의 에너지 충전소가 존재하는데 각각의 충전소에서 충전할 수 있는 에너지의 양이 모두 다르다.

이 때 N개의 충전소 중 어떤 지점에서 출발하여야 모든 충전소를 순회하고 원 지점으로 올 수 있는지 그 시작 지점을 반환하라.

이 때 자동차가 특정 지점으로 갈 때 정해진 양의 에너지를 소모하며 자세한 사항은 아래 예제를 참조한다.

만약 출발할 수 있는 지점이 여러 개일 경우 가장 작은 인덱스를 반환한다.

단, 자동차의 충전에는 제한이 없지만 첫 시작 에너지는 0으로 가정한다.

입력

• 먼저 충전소의 지점 개수를 위한 정수를 입력한다.
• 다음으로 각각의 충전소에서 충전할 수 있는 양을 지정한다. (띄어 쓰기)
• 마지막으로 충전소에서 다음 충전소까지 필요한 에너지 양을 지정한다. (띄어 쓰기)

출력

• 모든 지점을 방문할 수 있는 가장 작은 인덱스
• 해당 지점이 존재하지 않을 경우 -1을 반환한다.

예제

N이 5이고, 충전할 수 있는 양이 1, 3, 5, 6, 15, 그리고 필요한 양이 2, 3, 6, 5, 8로 주어졌다고 가정하면 각각의 N을 0번 인덱스부터 4번 인덱스라 하자.

0번 인덱스를 선택할 경우 시작 에너지가 0이고, 다음 충전소(1번 인덱스)까지 가기 위해서는 2만큼의 에너지가 필요하다.

그러나 0번 충전소에서 가능한 최대 양은 1이므로 모두 순회하는 것은 불가능하다.

다음으로 1번 인덱스를 시작 점이라 가정하면, 1번에서 2번을 가는 경우 필요한 에너지는 3이고, 충전할 수 있는 에너지는 3이다.

따라서 1번에서 2번으로 이동할 수 있다. 그러나 2번에서 충전량이 5이고 이동에서 필요한 양이 6이므로 1번 인덱스 역시 정답이 될 수 없다.

이와 같은 원리로 정답은 4번 인덱스가 반환된다.

 

A.

 

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 57 58 59

#include <iostream> #include <sstream> #include <string> #include <vector>   using namespace std;   int isEnableDrive(const vector<int> &E, const vector<int> &C) {   int eSum = 0, cSum = 0; for (int i = 0; i < E.size(); i++) { eSum += E[i]; cSum += C[i]; } if (eSum < cSum) return -1;   int startIdx, i; for (i = 0; i < E.size(); i++) { startIdx = i; int cnt = 0, energy = 0; while (cnt != E.size()) { energy += E[startIdx]; energy -= C[startIdx]; if (energy < 0) break; else cnt++;   startIdx++; if (startIdx == E.size()) startIdx -= E.size(); } if (cnt == E.size()) return i; } if (i == E.size()) return -1; }   int main(int argc, const char *argv[]) { int T = 0, N = 0;   for (int i = 0; i < T; i++) { vector<int> E, C; cin >> N;   for (int i = 0; i < N; i++) { int energy = 0; cin >> energy; E.push_back(energy); }   for (int i = 0; i < N; i++) { int cost = 0; cin >> cost; C.push_back(cost); }   cout << isEnableDrive(E, C) << endl; } }

먼저 전체 충전 가능한 에너지의 합보다 소비 에너지가 적을 경우 순환하는 것은 불가능하다.

따라서 이 경우는 자연스럽게 -1을 리턴하고, 그 외 경우에 대하여 각각의 인덱스를 기준으로 충전 가능한 에너지와 소비해야 할 에너지의 차이를 계산하여 탐색을 시작한다.

결과적으로 탐색이 완료된 인덱스(cnt만족)에 대해서는 해당 인덱스를 반환하고 종료한다.

만약 모든 지점을 다 탐색하여도 결과가 나오지 않은 것은 i == E.size()라 판단하였다.