BOJ 1876 튕기는 볼링공
문제 내용
폭이 105cm인 레인의 중간 선 위에 지름 12cm인 핀과 지름 20cm인 공이 있습니다. 핀의 중심은 공의 중심으로부터 미터만큼 떨어져 있습니다. ()
공이 레인의 양쪽 벽을 만나면 입사각과 반사각이 같게 반사됩니다. 공을 중간 선 기준으로 도 각도로 출발시키면 공이 핀과 만나는지 판별하세요. ()
문제 풀이
스포일러
공을 벽에 반사시키면서 시뮬레이션하는 것은 실수할 여지가 많기 때문에, 공 대신 핀을 반사시키는 방법을 생각할 수 있습니다.
공의 중심은 레인 내부의 85cm 폭을 갖는 구간에서 이동하므로, 공을 점으로 바꾸고 레인을 85cm로 줄일 수 있습니다. 또한, 공의 중심과 핀의 중심 사이의 거리가 16cm 미만이 되는 지점이 있는지 확인하는 것으로 문제를 바꿀 수 있습니다.
공이 반사될 때마다 대신 핀을 반사시키면, 핀은 아래쪽으로 85cm씩 이동합니다. 따라서 이러한 모든 핀의 위치에 대해서 공이 굴러가는 직선과의 거리를 구해 볼 수 있습니다. 이므로, 핀의 위치가 직선을 넘어갔을 때 브루트포스를 종료하면 충분히 빠르게 동작할 것이라고 예상할 수 있습니다.
이제 핀과 직선 사이의 거리를 구해야 합니다. 직선의 방향이 각도로 주어졌으므로, 공의 초기 위치를 원점으로 두고 핀의 위치를 도만큼 회전 변환한 후 좌표를 확인하는 것으로 대체할 수 있습니다. 도가 라디안이라고 하면 를 만큼 회전한 점의 좌표는 로 구하면 됩니다.