[백준] 13249 공의 충돌 (파이썬)

골드 Ⅴ

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

13249번: 공의 충돌

 

📄 문제

• 무게가 모두 같고, 크기가 0인 공 N개가 일직선 위에 놓여져 있다.
• 오른쪽으로 굴러가는 공과 왼쪽으로 굴러가는 공이 같은 속도로 충돌하면, 속도는 변하지 않고 공의 진행 방향만 바뀌게 된다.
• 공 N개의 위치가 주어진다.
• 효빈이는 공 N개의 진행 방향(오른쪽, 왼쪽)을 같은 확률로 결정한다.
• 시간 0일 때, 효빈이는 공을 결정한 방향으로 동시에 1초에 1만큼 이동하는 속도로 굴린다.
• T초 후에 공이 충돌한 횟수의 기댓값을 구하는 프로그램을 작성하시오.
• (T초에 충돌한 것도 포함해야 한다)

 

---

💡 아이디어

1.  공이 구분되지 않고 충돌후 속도가 변하지 않으므로,  방향이 바뀌면 다른 공이 그 자리를 대체한다.
   • 공이 대체되므로 충돌 후에도 같은 방향을 유지한다고 생각하면된다.
2. 임의의 두 공(nC2) 사이의 거리가 2t 이하이면서, 공이 마주보며 운동할 때만(1/4의 확률) 부딪힌다.
   
   • 거리가 2t 이하여야지 충돌한다.
   • 공 하나 당 오른쪽, 왼쪽으로 움직일 수 있다.
     • → →
     • ← ←
     • ← →
     • → ←
   • 전체 4가지 경우 중에 → ← 방향 일 때 만 공이 부딪힌다. (1/4 확률)

 

📝 문제 풀이 (Code)

import sys
input = sys.stdin.readline

n = int(input()) # 공의 개수
posi = list(map(int,input().split())) # 각 공의 위치
t = int(input()) # 시간

posi.sort()
cnt = 0

for i in range(n-1):
    for j in range(i+1, n):
        if (posi[j]-posi[i]) <= 2*t:
            cnt += 1

print(cnt/4)