[#29702] 이상한 호텔의 송이

문제

#29702 이상한 호텔의 송이
Silver4
적용 알고리즘: X(완전 이진 트리)

---

풀이 방법

• 방을 출력하는 방법이 까다롭기 때문에 방 출력 함수를 만든다.
• 현재 층에서 몇 번째 노드인지는 현재 노드의 번호 - 이전 층을 완전이진트리로 했을 때의 자식 수

코드 흐름

1. 층을 입력받는다. 노드의 수가 1에 도달할 때까지 2-5의 과정을 1번 방에 도달할 때까지 반복한다.
2. 현재 노드의 수를 활용하여 현재 노드가 있는 트리의 높이를 구한다.
3. 현재 있는 트리의 높이-1을 하여 현재 노드가 현재 층에서 몇 번쨰 자식인지 구한다.
4. 층을 제외하고 호까지의 자릿 수는 총 18자리이다. 0의 개수는 18 - len(호수)개이다.
5. 현재 층 수와, 구한 0, 그리고 호수를 합쳐 방 번호를 만든다.
6. 위에서 구한 방 번호를 반환하고, 1-5의 과정을 테스트 케이스 개수만큼 반복한다.

코드

import math

def print_room(k):
    height = math.ceil(math.log2(k + 1))

    sub = 2 ** (height - 1) - 1

    room_floor = str(height)
    room_num = str(k - sub)
    zeros = "0" * (18 - len(room_num))

    room_full = room_floor + zeros + room_num
    return room_full


t = int(input())

for i in range(t):
    n = int(input())
    while (n >= 1):
        print(print_room(n))
        n = math.floor(n / 2)

체감 난이도: 3/5
진짜 진심으로 왜 틀렸는지 모르겠다.