AMC 8 · 2024 · #14

Z로 들어오는 모든 경로는 Z로 향하는 세 화살표 — M에서, Y에서, C에서 — 중 정확히 하나로 끝나야 한다. 그래서 모든 경로는 빠지는 것도 두 무리에 걸치는 것도 없이 세 무리로 나뉘고, 전체 최단 경로는 그것을 담고 있는 무리 안에 있다.

한 무리 안에서 모든 경로는 Z로 가는 똑같은 하나의 화살표로 끝난다. 그래서 각 경로의 길이는 A에서 그 마을까지 가는 여정에 고정된 화살표 길이 하나를 더한 것이고, 마지막 부분이 무리 전체에서 동일하므로 그 마을까지 가장 짧은 거리로 도달하는 경로가 바로 합계가 가장 작은 경로이다. 이것이 각 무리의 최단이 그 마을까지의 최단 거리에 그 고정된 화살표를 더한 값인 이유이다.

각 무리는 하나의 마을 합계를 남기고, 전체 답은 이 셋 중 가장 작은 것이다. 세 합계를 늘어놓고 둘씩 비교할 때, 가장 작은 것이 가운데 것보다 작고 가운데 것이 가장 큰 것보다 작으면 가장 작은 것은 가장 큰 것보다도 작다. 그래서 한 값이 다른 두 값보다 작음이 확인되어 모든 경로의 최단 거리가 된다.

여기서 대입한 M, Y, C까지의 최단 거리는 마을마다 하나씩 차곡차곡 쌓아 온 누적 합계이다. 이것을 다시 쓰는 것이 옳은 이유는 화살표 길이를 단계별로 나누어 더하고 묶음을 다시 지어도 경로 전체의 화살표를 한 번에 더한 것과 같은 합이 되기 때문이다.