[Python] 13249번 공의 충돌

 

https://www.acmicpc.net/problem/13249

13249번: 공의 충돌

---

 

23/08/24

 

 

매우 유명한 애드혹 문제에 기댓값을 섞은 문제로, 아이디어만 알면 쉽게 구현할 수 있는 문제이다.

---

 

첫 번째 접근 방식:

 

 

먼저, 이 문제의 아이디어의 원천이 되는 한 문제를 보자.

 

https://www.acmicpc.net/problem/4307

4307번: 개미

4307번 문제에서는 개미의 크기를 생각하지 않으며, 모든 개미의 속력이 같고, 개미가 서로 만나면 반대방향으로 똑같은 속력으로 멀어진다는 점에서 이 문제의 상황과 동일하다.

 

물리학을 배웠던 사람이라면 알 수도 있을 내용이지만, 이는 완전탄성충돌 문제에서 나오는 속도 교환이라고 생각해도 된다.

 

속도 교환이란, 두 대상이 질량이 동일하고 완전 탄성 충돌을 한다면 이때, 서로의 속도가 바뀌어지는 것을 이야기한다.

 

4307번 문제에서는 개미가 서로 만나면 서로 멀어지는 방향으로 똑같은 속도로 멀어진다고 했으므로, 서로의 속도가 바뀌었다고 볼 수 있다.

 

이를 이용하여 "충돌"의 아이디어를 "통과"의 아이디어로 바꿀 수 있다는 것이 4307번 문제의 핵심이었다.

 

 

이 문제 또한 마찬가지이다. 

 

물론, 실제로는 서로가 통과하는 것이 아니지만, 우리의 목적은 결국 몇 번 충돌했냐를 세는 것이기 때문에 그냥 단순화하여 생각해도 된다.

 

처음에 접근한 방법은 브루트포스였다.

 

우리는 공이 총 $12$개 있음을 알고있고, 공이 충돌한 건 단순하게 공이 통과한 것이라고 간주하기 때문에 나중에 있을 수 있는 위치가 기껏 해봤자 $2^{12}$개 밖에 존재하지 않음을 알 수 있다.

 

공이 여러 개 주어져 있는 상황에서 처음에 $a$라는 좌표에 공이 있었다면, $T$초 후에는 공이 $a+T$ 또는 $a-T$에 위치해 있음을 알 수 있다. (물론, 실제로는 같은 공이 아닐 수도 있지만 우리는 어쨌든 저 위치에 공이 있다는 것을 안다.)

 

따라서 공이 나중에 있을 수 있는 위치를 파이썬의 product함수를 통해 구현해 주었다.

 

원래 위치를 now_pos라고 하고, product를 통해 만들어낸 $+T, -T$의 리스트들을 더해서 만든 새로운 나중 위치 리스트를 new_pos라고 했다.

 

이후 두 개의 공이 만나는지의 여부를 판단해 주었다.

 

itertools의 combinations함수를 통해 두 개의 공을 뽑고, 두 공의 현재 위치와 나중 위치를 비교했을 때 상대적으로 좌우가 바뀌어있다면 두 공은 서로 충돌했다는 것을 알 수 있으므로, 그때 충돌한 횟수에 $+1$을 해주었다.

 

이후 최종적인 기댓값은 $(전체 충돌한 횟수)/2^N$으로 구할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 13249번 공의 충돌
# 브루트포스, 확률론, 애드혹
'''
접근 방법:
충돌을 통과라고 생각해도 된다.
만난다는건 크기 순서가 뒤바뀌는 것이라고 생각해도 된다.
'''
import sys
input = sys.stdin.readline
from itertools import product, combinations

N = int(input())
now_pos = list(map(int, input().rstrip().split()))
T = int(input())
total = 0
for tpl in product([-T, T], repeat = N):
    a = 0
    new_pos = []
    for i in range(N):
        new_pos.append(now_pos[i] + tpl[i])
    for i, j in combinations(range(N), 2):
        if now_pos[i] < now_pos[j]:
            if new_pos[i] >= new_pos[j]:
                a += 1
        else:
            if new_pos[i] <= new_pos[j]:
                a += 1
    total += a
print(f'{total/(2**N):.15f}')

---

 

두 번째 접근 방식:

 

 

첫 번째 접근 방식을 조금 생각해 보면, 처음 위치와 나중 위치 리스트를 일일이 만들어줄 필요가 딱히 없다.

 

그냥 두 공이 만나려면, 두 공 사이의 떨어진 거리가 서로 $2T$보다 같거나 작은 상태에서 왼쪽 공이 오른쪽 방향으로, 오른쪽 공이 왼쪽 방향으로 가기만 하면 된다.

 

두 공을 뽑았을 때 두 공이 움직일 수 있는 방향의 가짓수는 좌 우/우 좌/좌 좌/우 우로, 총 $4$개이다.

 

이 중 두 공이 만나려면 방향이 우 좌 여야만 만날 수 있다.

 

즉, 넷 중에서 하나만 실질적으로 기댓값에 기여하므로, 기댓값의 선형성에 의하여 전체 기댓값에 $0.25$씩을 더해주면 된다.

 

따라서 combinations을 사용해 두 공을 뽑고, 두 공 사이의 떨어진 거리가 서로 $2T$보다 작은 경우 전체 기댓값에 $0.25$씩을 더해주면 총기댓값을 구할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

 

'''
접근 방법:
두 공의 충돌 여부 = 두 공의 통과 여부
두 공이 만나는 경우는 좌우, 우우, 좌좌, 우좌 중 우좌 일때만 만남
따라서 두 공의 모든 조합을 살펴보고, 그 중 만날 수 있다면
우좌일때만 만나므로, 즉, 4가지 경우중 1가지 경우만 되므로
기댓값의 선형성에 의해 전체 기댓값에 1/4을 더하면 된다.
'''
import sys
input = sys.stdin.readline
from itertools import combinations

N = int(input())
now_pos = list(map(int, input().rstrip().split()))
T = int(input())
total_expected_value = 0

for i, j in combinations(now_pos, 2):
    if abs(i-j) <= 2*T:
        total_expected_value += 0.25
print(total_expected_value)