문제
https://www.acmicpc.net/problem/16891
질량이 1인 A 물체를 향해 질량이 N^2인 B가 돌진합니다. A와 B가 부딪혔을 때, 멈춰있던 A는 B의 영향을 받아 벽쪽으로 튕겼다가 다시 움직일 것입니다. 이때 A가 B와 벽에 부딪히는 횟수는 모두 몇번일까? 가 문제에서 요구하는 정답입니다.
가능한 경우의 수
나타날 수 있는 경우의 수는 21가지입니다. 문제에서는 마찰을 무시하고 탄성 충돌만을 고려한다는 점을 기억하셔야 합니다.
A와 B가 왼쪽 방향으로 가고 있을 때
- A의 속도가 더 빠른 경우
- B의 속도가 더 빠른 경우
A와 B가 오른쪽 방향으로 가고 있을 때
- A의 속도가 더 빠른 경우
- B의 속도가 더 빠른 경우
A가 왼쪽, B가 오른쪽 방향으로 가고 있을 때
- A의 속도가 더 빠른 경우
- B의 속도가 더 빠른 경우
A가 오른쪽, B가 왼쪽 방향으로 가고 있을 때
- A의 속도가 더 빠른 경우
- B의 속도가 더 빠른 경우
A가 멈춰있고 B가 왼쪽 방향으로 가고 있을 때
A가 멈춰있고 B가 오른쪽 방향으로 가고 있을 때
A가 왼쪽 방향으로 가고 B가 멈춰있을 때
A가 오른쪽 방향으로 가고 B가 멈춰있을 때
A와 B 모두 멈춰있을 때
가능한 모든 경우를 나열해보았습니다. 각각의 경우는 충돌하면서 다른 경우로 바뀔 것이고, 더 이상 부딪히지 않는 경우도 생길 것입니다.
더 이상 부딪히지 않는 경우
- A와 B가 오른쪽 방향으로 가고 있을 때, B의 속도가 더 빠른 경우
- A가 멈춰있고 B가 오른쪽 방향으로 가고 있을 때
- A와 B 모두 멈춰있을 때
이렇게 3가지의 상황에 도달하게 된다면, 절대 충돌이 발생할 수 없습니다.
입력으로 주어지는 N의 크기는 500이 최대이고, 시간 제한을 3초나 줬기 때문에 반복문을 통해 시뮬레이션을 돌리면서 값을 구하기 충분하다는 것을 추측할 수 있습니다.
주의 할 점
마찰을 무시하기 때문에 A가 벽에 부딪히더라도 원래 속도에서 운동 방향만 반대가 됩니다. 문제에서는 왼쪽에서 오른쪽으로 가는 것을 양수로 두었기 때문에, 운동 방향의 반대는 부호의 반대로 생각해야 합니다.
또한, 속도를 구하는 공식을 사용하며 나눗셈을 하다 몫이 0 밑으로 내려갈 상황이 오기도 합니다. 이때 정수형으로 연산하게 되면 그대로 0이 되어버리면서 추후에 곱셈 연산을 하더라도 값이 올바르게 들어가지 않으면서 오차가 발생합니다. 꼭 실수형으로 연산해야 문제에서 원하는 값을 구할 수 있습니다.
1차 시도
#include <stdio.h>
double g(double n) {
return (1 - n * n) / (1 + n * n);
}
int main() {
int r = 0;
double n, a = 0, b = -100;
scanf("%lf", &n);
while (1) {
double c = g(n) * a + n * n * 2 / (1 + n * n) * b;
double d = 2 / (1 + n * n) * a - g(n) * b;
a = c, b = d;
r++;
if (a < 0 && a < b) {
a *= -1;
r++;
}
if (a > 0 && b > 0 && a < b) break;
if (!a && b > 0) break;
if (!a && !b) break;
}
printf("%d", r);
}c와 d는 각각 A와 B가 부딪히고 난 후의 속도를 의미합니다. 만약 A가 왼쪽 방향으로 가고 있을때 A가 B보다 작다면(A가 벽쪽으로 충돌하기 직전까지 B와 충돌할 상황이 일어나지 않는다면), 벽에 부딪혔으니 카운팅을 해주고 부호를 바꿔줍니다. 마찰이 없고 1차원 평면이기 때문에 속도가 그대로 유지되어 좌표처럼 특정 위치를 구할 필요는 없습니다.
종료 조건은 위에서 설명한 것처럼 걸어주고, 실수형 연산만 잘 해준다면 문제에서 원하는 값을 도출해낼 수 있습니다.
운이 좋게 한번에 맞았습니다. C언어로 해서 그런가 메모리와 속도 둘 다 준수해서 1페이지도 먹었네요 :) 근무중인 회사에서 물리학과 나온 팀원분께 문제를 추천해드렸다가 역으로 풀릴것같은 가능성을 받아버려서 풀어버렸습니다 ㅎㅎ; 그동안 풀어왔던 문제랑은 결이 달라서 조금 신선하네요.
풀고나서 친구한테 공유했다가
이런 영상이 있다는 사실을 알았습니다. 푼 문제와 정확히 같은 주제인데, 신기한건 10의 제곱수 단위로 커질때마다 부딪히는 횟수가 원주율이 나온다는 것입니다. 제출한 코드로 테스트해보니 정말 원주율의 앞 자리수가 나오는걸 보고 놀라웠습니다.
언젠간 물리도..? 공부해볼 날이 오지 않을까 싶네요.
