BOJ 2078 무한 이진 트리

무한한 크기의 이진 트리가 있는데 루트에는 (1, 1)을 할당하고
루트의 자식들부터는 다음과 같은 규칙에 의해서 할당한다.
어떤 노드에 (a, b)가 할당되었을 때, 그 노드의 왼쪽 자식은 (a+b, b), 오른쪽 자식은(a, a+b) 가 할당된다.

직접 조금 그려봤는데, 루트를 기준으로 반으로 나눴을 때 양쪽이 대칭된다. 그리고 루트 이후로는 할당된 숫자의 쌍 a, b가 서로 같은 경우는 없다. (a+b, b 혹은 a, a+b이므로 항상 한쪽이 더 클 수 밖에 없다.) 그리고 확실하게 증명한 것은 아니지만(물론 대칭된다는 것도 확실하게 증명한 것은 아니다) 두 개이상의 같은 숫자 쌍이 할당될 일은 없을 것 같다. 즉 할당 된 숫자 쌍(a, b)는 유일할 것이고 문제에서 구하라고 하는 것은 루트부터 주어진 숫자쌍까지의 최단거리에서 왼쪽 자식으로 향하는 횟수와 오른쪽 자식으로 향하는 횟수인데 (a, b)가 유일하다면 최단거리란 말에 큰 신경 안써도 될 것 같다.

근데 어떻게 구할까...a, b는 무려 최대 20억... 제한 시간은 1초.

일단 생각해보니 거꾸로 추적하면 root까지 가는 경로를 알 수 있을 것 같아보인다. 물론 시간안에 들어올 수 있을지는 모르겠지만 맨 왼쪽과 맨 오른쪽 라인을 제외하면 수가 큰 차이로 커지기 때문에 맨 왼쪽 과 맨 오른쪽 라인의 경우(숫자 쌍 중 하나가 1인 경우임)만 미리 계산을 해두면 될 것 같기도 하다. (계산하기도 쉽다 그냥 1이 아닌 숫자-1이 이동한 횟수이다. 1이 아닌 숫자가 왼쪽에 있으면 왼쪽으로 이동한 횟수, 오른쪽에 있으면 오른쪽으로 이동한 횟수- 그러니까 미리 계산할 필요없이 (n, 1)이나 (1, n)에 도달하면 횟수를 바로 알 수 있다!)
어떻게 거꾸로 추적하냐면, 예를들어 예제로 주어진 (3, 4)를 보면 오른쪽 값이 더 크다. 오른쪽 값이 더 크다는 것은 오른쪽으로 왔다는 것이다(오른쪽으로 내려가면 a, a+b이므로) 그리고 직전 값도 알아낼 수 있는데, 바로 왼쪽 값(a)은 그대로, 오른쪽 값은 오른쪽 값에서 왼쪽 값(a)를 뺀 것이다. 그렇게 거꾸로 가면서 횟수를 기록하면서 (1,1)도달하거나 (n, 1), (1, n)에 도달할경우 종료할 수 있다.

한 번 풀어봐야겠다.
AC를 받긴 했다. 그런데 시간이 무려 648ms...맞은 사람 목록을 보니 대부분 0ms...
다른 분들의 소스 코드를 보니 나랑 방식은 비슷한데, 차이점은 바로 left, right개수를 셀 때 나처럼 1을 더해주는 것이 아니라, b를 a로 나눈 값이나 a를 b로 나눈 값을 더해주고, a, b를 갱신할 때는 빼주는 게 아닌, %연산을 해서 나머지로 갱신을 해준다...
대충 예제를 가지고 해보니 그래도 맞는 것 같긴한데 왜 저렇게 하는지는 아직 잘 모르겠다.

생각을 해보는 중인데, 생각을 하다가 이 문제 관련 글에서 테스트 케이스를 추가해달라는 글을 봤는데, 그 테스트 케이스의 경우 내가 한 방법대로 하면 시간초과가 나는 케이스이다. 바로 3 2000000000인데, 내 방식대로 하면 20억에서 3씩 계속 빼는데.. 일단 내가 직접 돌려도 오래걸리는게 보이고, 대략 6-7억번은 돌기 때문에 당연히 시간초과이다.

다른 분들이 푼 방법을 다시 생각해보면, 일단 그래프에서 왼쪽으로 가면 왼쪽이 커지고 오른쪽으로 가면 오른쪽 숫자가 커지는데, (a+b, b / a, a+b 이므로...) 오른쪽으로만 간다고 해보면 a, b에서 시작해서 a, a+b, -> a, a+a+b -> a, a+a+a+b->...이런식으로 a씩 증가하게 된다. 그리고 b는 a보다 클리가 없는 것이, 오른쪽으로 가는 시작점은 분명 (1,1)루트이거나 왼쪽에서 온 점이기 때문에 시작점에서는 a가 b보다 큰 상태이다. 그렇기 때문에 (x, y)에서 y가 더 큰 경우에는 y/x의 값이 오른쪽으로 연속해서 온 횟수이고, y%x값이 오른쪽으로 이동하기 시작하는 노드에 할당된 숫자 쌍의 b값이 될 것이다. a값은 x값 그대로 일 것이고

근데 이런 생각이 들 수 있다. 이렇게 나누기로 해도 지그 재그로(왼쪽, 오른쪽) 가는 경로라면 시간단축을 별로 못할텐데? 하지만 생각해보면 그냥 한쪽 방향으로만 이동할 경우 a값 혹은 b값만큼만 커짐에 비해서, 지그 재그로 양쪽 방향 번갈아 이동하면 a+b값이 누적되면서 훨씬 빠르게 커지기 때문에 N제한인 20억까지 가는데 별로 안걸릴 것이다. 한 번 코드를 짜서 몇번 만에 (1,1) 20억 정도까지 가는지 계산해보겠다. 이 코드 짜는데도 조금 애를 먹었는데, while문 탈출 조건을 20억 이상으로 해야하는데(20억이 없을 수도 있으므로) 20억으로 지정해놨다가 무한루프... 여튼 짜봤더니 놀라운 결과가 나왔다.
1. 확인하기 위한 코드


2. 실행 결과

좌, 우 합해서 96번 만 이동하면 20억이 넘는다. 그래서 지그 재그로 가는 것은 문제 없다는 것을 알 수 있다.

갑자기 그럼 한쪽으로 좀 가다가 적절히 꺾고 하면 좀 오래걸리지 않으려나... 하는 생각도 들지만 그래도 저렇게 나누는 방식으로 하면 많이 단축될 것 같다.
다른 분들이 푼 방식이 맞는 방식이고 내가 원래 했던 방식은 시간초과가 나는 방식이므로 다른 분들이 푼 방식으로 풀어봐야겠다.