[백준] 31793. 공 굴리기

Jeeho Park (aquashdw)·2025년 1월 18일

얼마전 Solved.ac에서 백준 플래티넘을 찍었다.

몇년전만해도 알고리즘에 큰 관심 없었는데, 다음주 중에 400일 스트릭을 달성할 예정이기도 해서, 감회가 새롭다. 물론 여전히 알고리즘은 어렵다.....

이번주 일때문에 바빠서 글감이 없기도 하니, 최근에 풀었던 재밌는 문제 하나 리뷰해 보자.

공 굴리기

문제는 직접 가서 보자. 문제에서는 공의 숫자라고 표현되었지만, 그 숫자의 공이 들어가려면 결국 그만큼의 공을 굴려야 함으로, 생각하기에 따라 " $K$ 개의 공을 굴렸을 때 마지막 공이 멈추는 노드를 찾기"라고 번역해도 될것이다. 마치 옛날에 공 넣으면 어디로 굴러가는지 지켜보는 장난감이 생각났었다. 다만 여기는 확률적으로 좌우로 떨어지는게 아닌 떨어질 위치가 정해져 있다는 것.

포화 이진트리에서, 루트부터 공을 굴려서, 공이 오른쪽 왼쪽 번갈아서 구른다는 것, 그리고 서브트리도 비슷한 규칙으로 구를 것이라는 것 까지는 금방 유추가 가능했다. 처음에는 양쪽 서브트리 모두 비었으니 루트 기준으로 오른쪽에 먼저 굴리고, 그 다음 왼쪽 서브트리가 공이 더 적으니 왼쪽으로 굴리는 것이다. 그럼 다시 같아져서 오른쪽, 그 뒤 다시 왼쪽, 그러다 전부 찰 때까지 반복하는 것이었다.

그리고 각 서브트리의 경우도, 서브트리 기준에서 루트의 번호가 홀수냐 짝수냐의 차이일 뿐, 같은 규칙으로 공을 굴리게 된다. 즉 재귀로 해결하는게 편할 것이다.

공이 멈추는 상황

재귀로 해결하기로 했으면 가장 먼저 확인할 것이 종료 조건이었다. 이는 문제에서 이미 주어졌는데, 공 굴리는 규칙 2번에 있다.

현재 정점에서 공을 더 이상 굴릴 수 없다면 현재 공을 굴리는 것을 멈춘다.

포화 이진트리는 노드의 갯수가 정해져 있다. 깊이가 $N$ 이라면 $2^N - 1$ 개의 노드가 있다. 그렇다면 루트를 제외한 노드의 갯수는 $2^N - 2$ 개이므로, 남은 공의 갯수가 $2^N - 1$ 라면 루트에 공이 머무르게 된다. 즉, 노드의 갯수와 공의 갯수가 동일할 때, 루트에 공이 머문다는 의미다. 그 외의 상황이라면 공이 반씩 서로 다른 서브트리로 움직이게 된다. 서브트리로 이동하면 높이는 한칸 작아지므로, 그 시점에서 노드의 갯수와 공의 갯수를 조정하면 된다.

위를 종합해서 재귀호출을 위해, 서브트리에 들어온 공의 갯수, 서브트리의 노드의 갯수, 그리고 전체 트리 기준에서 노드의 번호를 매개변수로 받고, 공의 갯수와 서브트리의 노드의 갯수가 동일해질 때 그 값을 반환하도록 메서드를 정의했다.

private static long find(long balls, long totalNodes, long nodeNum) {
    if (balls == totalNodes) return nodeNum;
    // ...
}

왼쪽이냐 오른쪽이냐

다음 문제는 서브트리의 상황에 따라 왼쪽이 먼저냐, 오른쪽이 먼저냐는 문제가 있었다.

양쪽 서브트리에 담긴 공의 갯수가 같을 경우, 노드의 번호가 홀수면 오른쪽, 짝수면 왼쪽으로 공이 굴러간다.
노드의 번호가 짝수든 홀수든 공은 번갈아가며 들어가게 된다.

공이 양 서브트리에 번갈아가며 들어가게 된다는 건, 짝수 번째 공들과 홀수 번째 공들이 각각 같은 서브트리로 들어간다고 볼 수 있을 것이다. 그리고 현재 노드의 번호는, 이전 서브트리의 루트 노드 번호를 $n$ 이라 할 때, 왼쪽 서브트리로 가면 $n \times 2$ , 오른쪽 서브트리로 가면 $n \times 2 + 1$ 이므로 이전 호출에서 쉽게 받아올 수 있다. 그래서 이 두 가지를 조합하면 이번 서브트리에 들어온 마지막 공이 왼쪽으로 갈지 오른쪽으로 갈지 결정할 수 있다.

이후 이를 정리했는데, 두 값의 짝수 홀수 여부가 같으면 오른쪽으로, 다르면 왼쪽으로 감을 확인할 수 있었다.

짝수 노드에서는 짝수 번째 공들이, 홀수 노드에서는 홀수 번째 공들이 오른쪽으로 간다.
짝수 노드에서는 홀수 번째 공들이, 홀수 노드에서는 짝수 번째 공들이 왼쪽으로 간다.

// evenBall && evenNode -> right
// evenBall && !evenNode -> left
// !evenBall && evenNode -> left
// !evenBall && !evenNode -> right
boolean evenNode = nodeNum % 2 == 0;
boolean evenBall = balls % 2 == 0;

마지막으로 다음 서브트리의 노드의 갯수와 굴러갈 공의 갯수를 조정해야 하는데, 이는 상대적으로 간단하다. 노드의 갯수는 현재 서브트리의 노드의 갯수 $M$ 을 기준으로 $(M - 1) / 2$ 로 구할 수 있고 (루트를 제외한 나머지의 절반), 공은 짝수 개일 경우 그냥 절반, 홀수 개일 경우 절반에 하나 더하면 된다.

끝

이상을 조합해서 재귀 함수(메서드)를 구성해 보았다.

private static long find(long balls, long totalNodes, long nodeNum) {
    if (balls == totalNodes) return nodeNum;
    // evenBall && evenNode -> right
    // evenBall && !evenNode -> left
    // !evenBall && evenNode -> left
    // !evenBall && !evenNode -> right
    boolean evenNode = nodeNum % 2 == 0;
    boolean evenBall = balls % 2 == 0;
    long next = (balls + (evenBall ? 0 : 1)) / 2;
    totalNodes = (totalNodes - 1) / 2;
    if (evenNode == evenBall) {
        return find(next, totalNodes, nodeNum * 2 + 1);
    }
    else {
        return find(next, totalNodes,  nodeNum * 2);
    }
}

좀더 나아가면, 공이 한개일 경우 굴러가는 방향이 고정되므로 나머지 연산을 스킵하는 등...이 가능할것 같지만 해당 내용은 구현하지 않았으니 패스!

문제가 구현문제로 분류가 되어있긴 하지만, 이진 트리에서 놀다보니 약간 이진 탐색 트리 느낌도 들었다. 세부 식은 조금 다르겠지만, 결국 최악의 경우 트리의 가장 밑바닥까지 탐색해야 하니까, 시간복잡도는 노드의 갯수를 기준으로는 $O(\log n)$ 이기도 할것이다. 다 풀고 생각해보니 그 부분이 재밌게 느껴졌던 듯.