[BOJ 27231, Python] 2023년이 기대되는 이유

문제 링크

BOJ 27231

분류

브루트포스 알고리즘, 백트래킹

설명

요즘 예전에 못 풀었던 문제가 그럭저럭 해결되는 모습을 보아하니 실력이 향상되었다는 느낌이 들어서 기분이 좋다.

이 문제의 경우도 마지막 시도는 5달 전에 대회에 출제된 시점이지만, 중간중간에 해결 기미가 보이지 않는 풀이법도 여러 번 끄적여봤었다.

마지막 시도가 여러 번 있는 이유는 딱 한 가지 조건이 부족했기 때문인데 이 조건이 빠진다고 왜 시간초과를 받아버리는지는 아직 이유를 잘 모르겠다. 나중에 보충할 수 있는 이유라면 좋겠다. → 밑 내용을 정리하다가 생각났다. 역시 블로그 정리가 최고다!

문제의 풀이 접근을 소개해보자면

• + 기호를 넣는 좌표를 비트마스킹을 활용하여 전수 체크
• 집합 혹은 중복을 허용치 않는 리스트에 넣고 정렬
• 제곱 크기를 늘려주면서 최종적으로 처음에 입력된 수 (아무리 잘게 쪼개봐야 이 수보다 클 수 없기 때문) 까지 존재하는 숫자 카운팅

그리고 여기서 문제가 생겼다.

0, 1로 구성된 수의 경우 단일 숫자로 쪼갠다면 아무리 제곱해도 계속 값이 변하지 않기 때문에 Hello, BOJ 2023! 를 출력해줘야 하지만 난 단순하게 1인 경우만 배제하고 있었다.

아무리 제곱해도 숫자가 증가하지 않았기 때문에 while문에 걸려서 시간 초과를 받았던 것이다! 해당 파츠를 확인하기 위해 단일 숫자들에 대해서 2가 넘는지 체크하고 2가 넘는 항이 없다면 무조건 Hello, BOJ 2023! 를 출력하는 것으로 엣지 케이스를 처리하여 정답을 받을 수 있었다.

풀이 코드

# 2023년이 기대되는 이유

import sys

input = sys.stdin.readline


def pow_target(target_num: int, exponent: int) -> int:

    result = 0

    now_number = target_num

    while now_number:
        result += pow((now_number % 10), exponent)
        now_number //= 10

    return result


testcase = int(input())
result_dict = dict()
output = []

for _ in range(testcase):

    target_number = input().rstrip('\n')

    if result_dict.get(target_number) is not None:
        output.append(result_dict[target_number])

    else:

        is_under_limit = True

        for each_element in list(target_number):
            if int(each_element) > 1:
                is_under_limit = False
                break

        if is_under_limit:
            result_dict[target_number] = 'Hello, BOJ 2023!'
            output.append('Hello, BOJ 2023!')
            continue

        length = len(target_number)

        check_list = []
        check_list.append(int(target_number))

        for i in range(1, 1 << length):

            calc_result = 0

            now_start = 0
            now_end = 0

            for j in range(length):

                if i & (1 << j):
                    now_end = j
                    if now_end:
                        calc_result += int(target_number[now_start : now_end])
                    now_start = now_end
                    
            calc_result += int(target_number[now_start : length + 1])

            if calc_result not in check_list:
                check_list.append(calc_result)

        else:
            result = 0

            check_amount = len(check_list)
            check_list.sort()

            max_value = check_list[-1]
            pointer = 0
            counter = 1

            while pointer < check_amount:
                now_result = pow_target(int(target_number), counter)

                # 종료 조건 1
                if now_result > max_value:
                    break

                while pointer < check_amount and now_result > check_list[pointer]:
                    pointer += 1

                # 종료 조건 2
                if pointer >= check_amount:
                    break

                if now_result == check_list[pointer]:
                    result += 1

                counter += 1

            result_dict[target_number] = result
            output.append(result)

for result in output:
    print(result)