파이썬으로 일정한 간격의 돌을 수집할 때 필요한 총 이동 거리 구하기

문제 상황

달리기 대회를 개최한다고 가정해 보겠습니다. 도로 위에는 여러 개의 돌이 놓여 있고, 출발 지점에는 양동이 하나가 있습니다. 양동이는 첫 번째 돌에서 6단위 떨어져 있으며, 나머지 돌들은 서로 4단위씩 간격을 두고 일직선상에 차례로 배치되어 있습니다.

참가자는 양동이에서 출발하여 가장 가까운 돌을 집어 들고 양동이로 되돌아와 돌을 넣은 뒤, 다시 다음으로 가까운 돌을 가지러 달려갑니다. 이 과정을 모든 돌이 양동이에 담길 때까지 반복합니다. 돌이 n개 있다면, 참가자가 이동해야 하는 총 거리를 구해야 합니다.

예를 들어 n = 5라면 결과는 140입니다.
2×6 + 2×(6+4) + 2×(6+4+4) + 2×(6+4+4+4) + 2×(6+4+4+4+4) = 140

접근 방법

각 돌마다 왕복 거리를 계산하면 다음과 같습니다.

• 돌 1: (6+6) = 2×6 의 거리를 이동
• 돌 2: ((6+4)+(6+4)) = 2×(6+4) 의 거리를 이동
• 돌 3: ((6+4+4)+(6+4+4)) = 2×(6+4+4) 의 거리를 이동
• 돌 n: ((6+4×(n−1))+(6+4×(n−1))) = 2×(6+4×(n−1)) 의 거리를 이동

모든 돌에 대해 거리를 모두 더하면 다음과 같이 정리할 수 있습니다.

• D = 2×6 + 2×(6+4) + 2×(6+4+4) + … + 2×(6+4×(n−1))
• D = 2×[6 + (6+4) + (6+2×4) + … + (6+(n−1)×4)]
• D = 2×[6n + 4(1 + 2 + … + (n−1))]
• D = 2×[6n + 4(n(n−1)/2)]
• D = 2×[6n + 2(n(n−1))]

최종적으로 얻은 공식은 D = 2×(6n + 2n(n−1))이며, 반복문 없이 한 번의 연산만으로 답을 구할 수 있으므로 시간 복잡도는 O(1)입니다.

예제 코드

다음 파이썬 코드로 확인해 볼 수 있습니다.

def find_distance(n):
    return 2*(6*n + 2*((n-1)*n))

n = 5
print(find_distance(n))

입력

5

출력

140