BOJ - 18225 - 당구공을 넣자

문제

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

아이디어

다음 주에 당구 시뮬레이션 과제가 주어져서 연습 겸 당구 시뮬레이션 문제를 풀어보려다가 전혀 다른 문제임을 깨달았지만 결국 풀었다. 흑흑

정수론, 직선 구현 문제

반사 == 대칭 으로 접근하여 직선을 꺾지 않고 나아가게 두면 다음과 같은 풀이로 고칠 수 있다.

이러면 주어진 위치 좌표 $x,y$ 와 속도 $v_x,v_y$로 그려지는 직선에 대하여

당구대의 길이를 x길이 $D_x$, y길이 $D_y$라 할 때,

직선 위에 존재하는 $(nD_x,mD_y), n,m {\in} Z$ 를 찾는 문제가 된다.

직선을 $Ax+By=C$ 꼴로 쓴다면
$AD_x*n+BD_y*m=C$ 를 만족하는 정수해 $n,m$을 찾는 문제로 볼 수 있다.

부등 방정식의 정수해를 어떻게 찾을 것인가?

일단 $AD_x, BD_y, C$를 서로소가 되도록 최대공약수를 나눠준 뒤 케이스 분류를 하였다.

1. $C = 0$

$C$가 0인 경우 $(n,m) = (BD_y/gcd,-AD_x/gcd)$ 가 된다.

2. $C \not= 0$ 인데, 부등방정식의 해가 있는 경우

먼저 해가 있는지 없는지 어떻게 알 것인가?

3. 부등 방정식의 해가 없는 경우

이 경우 답은 -1일 것이다.

2번에서 많은 고민을 하다가 검색을 통해 베주 항등식과 확장 유클리드 알고리즘을 찾았다.

https://namu.wiki/w/%EB%B2%A0%EC%A3%BC%20%ED%95%AD%EB%93%B1%EC%8B%9D

요점은 $ax+by=gcd(a,b)$ 의 해는 반드시 존재하며
C가 gcd(a,b)의 배수라면 식의 양변에 우변이 C가 되도록 정수를 곱하면 되니 해가 존재하다는 것, C가 gcd(a,b) 배수가 아니라면 해가 존재하지 않는다.

따라서 케이스 2와 3을 나눌 수 있게 되었고 남은 것은 케이스 2에서 일반해들 중에서 직선으로 생각하였을 때 가장 먼저 만나는 해를 찾는 것이다. 가장 먼저 만나는 해는 원점에서 가장 가까운 첫 해일 것이다.

---

예제로 생각해보자.

백준에서의 예제는 모두 C가 0인 케이스이거나 C가 A,B의 공약수가 아닌 형태라 직접 만든 테스트 케이스

$D_x = 6,D_y=4,x=1,y=1,v_x=1,v_y=3$

이라면 처음 직선의 방정식은 $3x-y=2$

식에 $Dx,Dy$를 넣으면
$3nD_xx-mD_y=2 \rightarrow 9n-2m=1$이 된다.

$C = 1$은 9와 2의 최대 공약수의 배수이므로 정수해는 존재한다. 그러한 답은 $(1,4)$ 이고 $x=6,y=4,8,12,16$인 변에 부딪히게 되므로 답은 4가 된다. (모서리 부분 -1)

---

주어진 일차 부등방정식의 정수해는 확장 유클리드 알고리즘으로 특수해를 찾을 수 있었다.

특수해를 찾은 뒤 일반해 들 중 0에 가장 가까운 양수 해가 되도록 이동해주면 끝!

구현 부분은 따로 싣지 않겠습니다.

확장 유클리드 알고리즘과 베주 항등식에 관한 링크들

https://double-tap.tistory.com/46
https://8iggy.tistory.com/19
https://suhak.tistory.com/223
https://codepractice.tistory.com/79

---

결과

정수론을 공부해본 적이 없어서 어려웠습니다. 1차 부등 방정식을 풀 경우가 알고리즘에서는 꽤 많을 듯 한데 (뭐 경시대회 문제에서나?) 한번 당해봤으니 다음에는 더 빨리 풀 수 있을 것 같습니다. ㅎㅎ