원형 튜브에서 공이 몇 번 충돌하는지 계산하는 Python 프로그램

문제 개요

원형 튜브 안에 n개의 공이 들어 있다고 가정해 보겠습니다. 튜브의 길이는 100미터이며, 처음에 각 공은 '시작점'이라 부르는 기준 지점으로부터 i미터 떨어진 위치에 놓여 있습니다. 이후 공들은 제각각의 방향으로 튜브 안을 순환하며 이동하고, 이동 속도는 초당 0.1미터입니다.

두 공이 같은 지점에서 만나면 충돌이 발생하며, 충돌한 공들은 서로 이동 방향을 바꿉니다. 이 과정이 아주 긴 시간, 예컨대 10^9 + 6초 동안 계속된다고 할 때, 그동안 공들이 충돌한 총 횟수를 구하는 것이 이 문제의 목표입니다. 각 공의 시작점으로부터의 초기 거리가 입력으로 주어집니다.

예를 들어 입력이 input_array = [0, 10]이라면 출력은 400000입니다. 공은 두 개이고 시작선으로부터의 초기 거리가 주어집니다. 두 공의 이동 방향이 같으면 아무리 시간이 지나도 충돌하지 않지만, 방향이 서로 다르다면 주기적으로 마주치게 되어 한 공이 다른 공과 정확히 400000번 충돌하게 됩니다.

풀이 접근 방법

이 문제는 모든 충돌을 일일이 시뮬레이션할 필요 없이, 운동의 주기성을 활용한 수학적 규칙만으로 답을 구할 수 있습니다. 해결 절차는 다음과 같습니다.

1. 입력 리스트 input_array를 오름차순으로 정렬합니다.
2. size를 리스트의 크기로 설정합니다.
3. lap_count를 (10^5) × 2로 설정합니다. 이는 주어진 시간 동안 방향이 반대인 공들이 서로 마주치는 상대 바퀴 수에 해당합니다.
4. output을 2 × lap_count × (size // 2) × (size − size // 2)로 초기화합니다. 이 값은 서로 반대 방향으로 이동하는 공 쌍들이 만들어내는 기본 충돌 횟수입니다.
5. stop을 0으로 초기화합니다.
6. i를 0부터 size − 2까지 반복하며 인접한 두 공의 초기 위치를 확인합니다. 만약 input_array[i] + 1 == input_array[i+1], 즉 거리가 1미터인 공이 연속으로 존재한다면 추가 충돌이 발생하므로 output에 2를 더하고, stop을 1로 설정하여 같은 구간이 중복 계산되지 않도록 합니다.
7. 조건에 해당하지 않거나 이미 처리된 경우에는 stop을 0으로 되돌립니다.
8. 모든 반복이 끝나면 output을 반환합니다.

구현 예제

아래 파이썬 코드를 통해 실제 구현을 확인할 수 있습니다.

def solve(input_array):
    input_array.sort()
    size = len(input_array)
    lap_count = (10**5)*2
    output = 2*lap_count*(size//2)*(size - size//2)
    stop = 0
    for i in range(size - 1):
        if stop != 1:
            if input_array[i] + 1 == input_array[i+1]:
                output += 2
                stop = 1
            else:
                stop = 0
        else:
            stop = 0
    return output

print(solve([0, 10]))

실행 결과

입력:

[0, 10]

출력:

400000

마무리

이 문제의 핵심은 방대한 시간(10^9초 이상) 동안의 충돌을 하나하나 추적하는 대신, 주기적 운동의 성질을 이용해 수식 한 번으로 전체 충돌 횟수를 계산하는 것입니다. 알고리즘의 시간 복잡도는 정렬 과정에 의해 결정되어 O(n log n)으로 매우 효율적이며, 공의 개수가 늘어나더라도 빠르게 답을 구할 수 있습니다.