[Python] 16891번 탄성 충돌 / 22295번 twOBoOgEr

 

 

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

16891번: 탄성 충돌

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

22295번: twOBoOgEr

---

 

23/09/01

 

 

두 문제는 코드가 완벽하게 같은 것은 아니지만, 거의 비슷한 코드로 해결할 수 있는 문제로, 해결 방법을 올려보고자 한다.

 

---

 

첫 번째 접근 방식:

 

 

첫 번째 접근 방식은 다음 영상을 참조했다.

 

https://www.youtube.com/watch?v=HEfHFsfGXjs 

3b1b의 동영상

이 영상에서는 $N$이 항상 $100$의 제곱 수인 경우만을 다루고 있다.

 

하지만 문제에서 요구하는 상황은 일반적인 $N$에 대한 상황을 요구하므로 문제를 살짝 바꿀 필요가 있었다.

 

이에 대한 상황(일반적인 상황)은 영상의 원천이 되는 논문에 나와있었다.

 

https://www.maths.tcd.ie/~lebed/Galperin.%20Playing%20pool%20with%20pi.pdf

 

이 논문의 7번 단락에 적혀있는 Lemma 2에 의하면 부딪히는 횟수는 $[\pi / \alpha]$와 같고, 이때 $\alpha = \mathrm{arctan} \sqrt{m/M}$에 해당한다고 했다. 여기서, $M$과 $m$은 각각 무거운 물체의 질량과 가벼운 물체의 질량을 뜻한다.

 

$M = N$에 해당되고, $m$은 $1$이라고 주어져 있으므로, 이를 그대로 구현하면 된다.

 

유의할 점은 $N = 1$일 때를 예외처리 해줘야 한다.

 

---

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

# 22295번 twOBoOgEr
# 애드혹, 물리학
from math import atan, pi, sqrt
def P6(n):
    return 3 if n==1 else int(pi/atan(sqrt(1/n)))

# 16891번 탄성 충돌
# 애드혹, 물리학
from math import atan, pi, sqrt
def P6(n):
    return 3 if n==1 else int(pi/atan(sqrt(1/n)))
N = int(input())
print(P6(N*N))

 

---

 

두 번째 접근 방식:

 

 

사실 위의 논문을 제대로 이해하지 않고 문제를 해결한 터여서 조금 찝찝했기 때문에 실제로 시뮬레이션하는 방식으로 문제를 구현해 보았다.

 

먼저 종료 조건을 생각해 봤다.

 

두 물체가 더 이상 충돌하지 않고 끝나는 경우는 두 물체의 이동 방향이 서로 같으면서(벽에서 멀어지는 방향), 동시에 가벼운 물체의 속력이 무거운 물체의 속력보다 느려서 영원히 도달하지 못하는 경우이다.

 

이 조건을 만족시킨다면 종료를 시켜주고, 그렇지 않으면 while문을 통해 계속 반복시켜서 충돌 횟수를 $+1$해주는 방식을 채택했다.

 

두 물체가 부딪힌다면 두 물체의 속도가 바뀌게 되는데, 이에 대한 식은 문제에서 다음과 같이 주어졌다.

 

$$ v_1 = \frac{m_1-m_2}{m_1+m_2}u_1 + \frac{2m_2}{m_1+m_2}u_2 $$ 
$$ v_2 = \frac{2m_1}{m_1+m_2}u_1 - \frac{m_1-m_2}{m_1+m_2}u_2 $$

 

이때, $u_1, u_2$는 충돌 이전의 물체 속도, $v_1, v_2$는 충돌 이후의 물체 속도를 의미한다.

 

이 식을 이용하면 두 물체가 부딪힐 때의 물체의 속도를 구할 수 있다.

 

그리고 이때 충돌 횟수를 $+1$해준다.

 

안쪽에 있는 물체가 벽에 부딪히면 반대 방향으로 바뀌므로 이를 적용시키고 충돌 횟수를 $+1$해준다.

 

이 과정을 반복시키다가 종료 조건을 만족시키면 끝이다.

 

---

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

'''
접근 방법:
주어진 계산식을 활용하여 계산
'''
def main():
    N = int(input())
    if N == 1:
        print(3)
        return
    A, B = 1, N*N
    V_a, V_b = 0, -1
    count = 0
    while True:
        if V_a > 0 and V_b > 0 and V_a < V_b:
            break
        V_a, V_b = (A-B)*V_a+2*B*V_b, 2*A*V_a-(A-B)*V_b
        if V_a % (A+B) == 0 and V_b % (A+B) == 0:
            V_a, V_b = V_a//(A+B), V_b//(A+B)
        count += 1
        if V_a > 0 and V_b > 0 and V_a < V_b:
            break
        V_a = -V_a
        count += 1
    print(count)
main()

def P6(N):
    if N == 1:
        return 3
    A, B = 1, N
    V_a, V_b = 0, -1
    count = 0
    while True:
        if V_a > 0 and V_b > 0 and V_a < V_b:
            break
        V_a, V_b = (A-B)*V_a+2*B*V_b, 2*A*V_a-(A-B)*V_b
        if V_a % (A+B) == 0 and V_b % (A+B) == 0:
            V_a, V_b = V_a//(A+B), V_b//(A+B)
        count += 1
        if V_a > 0 and V_b > 0 and V_a < V_b:
            break
        V_a = -V_a
        count += 1
    return count