0부터 n-1까지 번호가 붙은 n개의 도시와 n개의 일방통행 도로가 있다고 가정해 봅시다. i번 도시에서는 (i + 1) % n번 도시로 이동할 수 있습니다(0 → 1 → 2 → ... → N-1 → 0). 우리에게는 자동차가 한 대 있고, 연료 탱크의 용량은 cap 단위입니다. 각 도시 i에 도착하면 fuel[i] 단위의 연료를 보충할 수 있으며, i번 도시에서 (i + 1) % n번 도시로 이동하는 데는 cost[i] 단위의 연료가 필요합니다.
이때, 자동차를 출발시켜 모든 도시를 한 바퀴 돌고 다시 출발한 도시로 무사히 돌아올 수 있는 출발 도시가 몇 개인지 구하는 것이 문제입니다.
예시로 이해하기
입력이 cap = 3, fuel = [3, 1, 2], costs = [2, 2, 2]라면 출력은 2입니다. 성공적인 출발이 가능한 경우는 두 가지입니다.
도시 0에서 출발: 탱크에 연료 3단위를 채운 뒤 2단위를 사용해 도시 1로 이동합니다. 이때 탱크에는 1단위가 남습니다. 도시 1에서 연료 1단위를 보충하면 2단위가 되고, 이를 모두 사용해 도시 2에 도착합니다. 도시 2에서 연료 2단위를 주유한 뒤 다시 2단위를 사용해 출발점인 도시 0으로 복귀합니다.
도시 2에서 출발: 연료 2단위를 채워 도시 0으로 이동합니다. 도시 0에서 3단위를 주유한 뒤 도시 1로 이동하면 연료가 1단위 남습니다. 도시 1에서 1단위를 더 보충해 2단위를 만든 후 도시 2로 복귀합니다.
반면 도시 1에서는 출발할 수 없습니다. 보유 연료가 1단위뿐인데, 도시 2로 이동하는 데만 2단위가 필요하기 때문입니다.
알고리즘 접근 방식
이 문제는 각 도시에서 출발할 때 필요한 추가 연료량(부족분)을 역방향으로 누적 계산하면 효율적으로 풀 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- n := fuel 배열의 길이
- req := 길이가 n인 배열을 만들고 0으로 초기화 (req[i]는 i번 도시에서 출발할 때 부족한 연료량)
- k를 0부터 1까지 두 번 반복:
- i를 n-1부터 0까지 감소시키며 반복:
- nexti := (i + 1) mod n
- req[i] := max(0, req[nexti] + costs[i] - fuel[i])
- 만약 min(req[i] + fuel[i], cap) - costs[i] < req[nexti]라면 0을 반환 (탱크를 가득 채워도 다음 구간을 통과할 수 없으므로 어떤 출발점으로도 완주 불가능)
- i를 n-1부터 0까지 감소시키며 반복:
- req에서 값이 0인 원소의 개수를 반환
원형 경로의 특성상 요구 연료량이 경계를 넘어 전달되기 때문에, 역방향 순회를 두 번 실행하면 모든 값이 안정화됩니다. 이 방식의 시간 복잡도는 O(n), 공간 복잡도는 O(n)으로 매우 효율적입니다.
파이썬 구현 예제
아래 코드를 통해 동작 방식을 더 잘 이해할 수 있습니다.
def solve(cap, fuel, costs):
n = len(fuel)
req = [0] * n
for k in range(2):
for i in range(n-1, -1, -1):
nexti = (i + 1) % n
req[i] = max(0, req[nexti] + costs[i] - fuel[i])
if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
return 0
return sum(1 for r in req if r == 0)
cap = 3
fuel = [3,1,2]
costs = [2,2,2]
print(solve(cap, fuel, costs))입력
3, [3,1,2], [2,2,2]
출력
2