원형 주유 문제란?
원형으로 배치된 N개의 주유소가 있습니다. 주유소 i에서는 gain[i]만큼 연료를 채워주지만, 다음 주유소까지 이동하는 데 cost[i]만큼 소모합니다. 연료 탱크는 처음에 비어 있고 용량 제한은 없습니다.
한 주유소에서 출발해 시계 방향으로 모든 주유소를 한 번씩 거쳐 제자리로 돌아올 수 있는 출발점을 찾는 것이 목표입니다. 가능한 출발점이 없으면 -1을 반환합니다.
알고노트에서는 이 문제를 친근하게 "한밤의 야식 트럭"으로 각색했습니다. 원형 순환로의 포장마차를 한 바퀴 도는 트럭의 출발점을 찾는 이야기죠.
핵심은 차이값(diff)
각 지점의 diff[i] = gain[i] - cost[i]를 생각하면 문제가 단순해집니다.
- •
diff[i] > 0→ 그 지점을 지나면 연료가 늘어남 - •
diff[i] < 0→ 연료가 줄어듦
전체 합이 음수면 어떤 출발점에서도 한 바퀴를 돌 수 없습니다. 전체 소모가 충전보다 크기 때문입니다. 따라서 가장 먼저 총합을 확인합니다.
왜 출발점을 다음으로 옮기나?
핵심 그리디 성질은 다음과 같습니다.
출발 후보 start부터 누적합을 더해 가다가 지점 i에서 처음으로 음수가 되었다면, start와 i 사이의 어떤 지점에서 출발해도 i를 넘지 못한다.
증명은 간단합니다. start에서 i까지의 누적이 음수라면, 중간 지점 j에서 출발한 j~i 구간의 합은 (start~i 합) − (start~j-1 합)입니다. start~j-1 구간은 i에서 처음 음수가 됐으므로 0 이상이었고, 따라서 j~i 합 ≤ start~i 합 < 0 입니다. 즉 j에서 출발해도 똑같이 i에서 막힙니다.
그래서 출발 후보를 i+1로 한 번에 점프하고 누적 탱크를 0으로 리셋해도 안전합니다. 이 점프 덕분에 한 번의 스캔, 즉 O(n)에 답을 찾습니다.
동작 원리
1단계. total = 0, tank = 0, start = 0으로 초기화합니다.
2단계. 각 지점 i에서 diff = gain[i] - cost[i]를 total과 tank에 더합니다.
3단계. tank < 0이면 start = i + 1로 옮기고 tank = 0으로 리셋합니다.
4단계. 스캔이 끝난 뒤 total >= 0이면 start를, 아니면 -1을 반환합니다.
여기서 "누적 갱신"과 "출발점 이동"은 서로 다른 동작입니다. 알고노트 시각화도 이 둘을 각각 별도 단계로 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(n) |
| 공간 | O(1) |
모든 출발점을 각각 한 바퀴 돌려보는 단순 풀이는 O(n²)이지만, 위 그리디 성질 덕분에 한 번의 스캔으로 O(n)에 해결합니다.
예시로 따라가기
gain = [2, 4, 1, 6, 3], cost = [4, 1, 5, 2, 2] 라면 diff = [-2, +3, -4, +4, +1], 총합 +2 입니다.
- •start=0: diff[0]=-2 → tank=-2 < 0 → start=1로 이동
- •start=1: diff[1]=+3 → tank=3, diff[2]=-4 → tank=-1 < 0 → start=3으로 이동
- •start=3: diff[3]=+4 → tank=4, diff[4]=+1 → tank=5
끝까지 살아남은 start=3이 정답입니다.
자주 하는 실수
- •총합 체크 누락:
total >= 0확인 없이 start만 반환하면 불가능한 경우를 못 거릅니다. - •리셋 타이밍: tank가 음수가 된 직후 즉시 start를 옮기고 tank를 0으로 리셋해야 합니다.
- •원형 처리 오해: 이 그리디는 모듈러 인덱싱 없이도 한 번의 선형 스캔으로 충분합니다(정답이 존재하면 유일).
알고노트에서 직접 확인하세요
차이값이 어떻게 누적되고, 탱크가 음수가 될 때 출발점이 어떻게 점프하는지 알고노트에서 단계별로 확인할 수 있습니다.