[Algorithm] C++/Python 백준 14924번 : 폰 노이만과 파리

폰 노이만과 파리는 알고리즘 문제를 통해 천재적인 사고방식을 탐구할 수 있는 흥미로운 주제이다. 이번 포스팅에서는 백준 14924번 문제 “폰 노이만과 파리"를 중심으로 문제를 설명하고, 효율적인 풀이 방법을 제시하고자 한다.

문제 : https://www.acmicpc.net/problem/14924

문제 설명

역사상 최고의 천재 중 하나로 손꼽히는 폰 노이만에게는 흥미로운 일화가 전해진다. 어느 날, 그의 동료는 폰 노이만의 천재성을 시험해보기 위해 다음과 같은 문제를 던졌다.

“200마일 길이의 철로의 양쪽 끝에 서 있는 두 대의 기차가 시속 50마일의 속도로 서로를 향해 출발했습니다. 이때부터 두 기차가 서로 충돌할 때까지 파리가 시속 75마일의 속도로 두 기차 사이를 왔다 갔다 했습니다. 파리가 이동한 거리는 모두 몇 마일일까요?”

폰 노이만은 이 문제를 1초의 망설임도 없이 150마일이라고 답했다. 그의 동료는 파리가 이동한 거리를 무한급수를 이용해 계산하려 했지만, 폰 노이만은 간단한 논리를 통해 빠르게 답을 도출한 것이다.

이 문제를 일반화하여, 두 기차의 속도 S, 파리의 속도 T, 그리고 처음 두 기차 사이의 거리 D가 주어질 때, 두 기차가 만날 때까지 파리가 이동한 거리 F를 계산하는 프로그램을 작성하는 것이 목표이다. 단, T > S이며, D는 2*S의 배수로 주어진다.

접근 방식

이 문제를 해결하기 위해서는 두 기차가 만날 때까지 걸리는 시간을 먼저 계산하고, 그 시간 동안 파리가 이동한 거리를 구하면 된다. 두 기차는 서로를 향해 동일한 속도로 움직이므로, 두 기차가 만나는 시간은 처음 거리 D를 두 기차의 속도 합인 2*S로 나눈 값이 된다.

파리는 이 시간 동안 시속 T마일의 속도로 이동하므로, 이동한 거리 F는 T와 만나는 시간의 곱으로 계산할 수 있다.

즉,

1
2
시간 = D / (2 * S)
F = T * 시간

이러한 단순한 계산을 통해 문제를 효율적으로 해결할 수 있다. 무한급수를 사용하지 않아도 되므로, 시간 복잡도는 O(1)이다.

C++ 코드와 설명

아래는 문제를 해결하는 최적화된 C++ 코드이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int S, T, D;
    cin >> S >> T >> D;
    
    // 두 기차가 만나는 시간 계산
    int time = D / (2 * S);
    
    // 파리가 이동한 거리 계산
    int F = T * time;
    
    cout << F;
}

코드 설명:

입력 받기: S (기차의 속도), T (파리의 속도), D (두 기차 사이의 초기 거리)를 입력받는다.
시간 계산: 두 기차가 만나는 시간 time을 D / (2 * S)로 계산한다.
거리 계산: 파리가 이동한 거리 F를 T * time으로 계산한다.
결과 출력: 계산된 거리를 출력한다.

예제:

입력:

1
50 75 200

출력:

1
150

이 예제에서 두 기차는 2시간 후에 만나며, 파리는 이 시간 동안 150마일을 이동하게 된다.

C++ without library 코드와 설명

아래는 stdio.h와 malloc.h만을 사용하여 작성한 최적화된 C++ 코드이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <stdio.h>

int main(){
    int S, T, D;
    scanf("%d %d %d", &S, &T, &D);
    
    // 두 기차가 만나는 시간 계산
    int time = D / (2 * S);
    
    // 파리가 이동한 거리 계산
    int F = T * time;
    
    printf("%d", F);
}

코드 설명:

입력 받기: scanf를 사용하여 S, T, D를 입력받는다.
시간 계산: D / (2 * S)를 통해 두 기차가 만나는 시간을 계산한다.
거리 계산: T * time을 통해 파리가 이동한 거리 F를 계산한다.
결과 출력: printf를 사용하여 결과를 출력한다.

이 코드는 C++ 표준 라이브러리를 사용하지 않고도 동일한 논리를 구현하였다.

Python 코드와 설명

아래는 문제를 해결하는 최적화된 Python 코드이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def main():
    S, T, D = map(int, input().split())
    
    # 두 기차가 만나는 시간 계산
    time = D // (2 * S)
    
    # 파리가 이동한 거리 계산
    F = T * time
    
    print(F)

if __name__ == "__main__":
    main()

코드 설명:

입력 받기: input().split()을 통해 S, T, D를 입력받고, map을 사용하여 정수로 변환한다.
시간 계산: D // (2 * S)를 통해 두 기차가 만나는 시간을 계산한다. 정수 나눗셈을 사용하여 시간의 정수 값을 보장한다.
거리 계산: T * time을 통해 파리가 이동한 거리 F를 계산한다.
결과 출력: print(F)를 사용하여 결과를 출력한다.

예제:

입력:

1
50 75 200

출력:

1
150

Python 코드 역시 C++ 코드와 동일한 논리로 문제를 해결하였다.

결론

백준 14924번 “폰 노이만과 파리” 문제는 간단한 수학적 계산을 통해 효율적으로 해결할 수 있는 문제이다. 두 기차가 만나는 시간을 먼저 계산하고, 그 시간 동안 파리가 이동한 거리를 구하는 접근 방식은 무한급수를 사용하는 것보다 훨씬 빠르고 간단하다. 이를 통해 문제 해결에 필요한 논리적 사고의 중요성을 다시 한 번 깨달을 수 있었다. 추가적으로, 입력 조건이 명확하게 주어졌기 때문에 예외 처리를 신경 쓸 필요 없이 문제를 해결할 수 있었다. 이러한 유형의 문제는 구현 실력을 키우는 데 큰 도움이 되며, 다양한 문제에 응용할 수 있는 기본적인 사고 방식을 배울 수 있다.