[BOJ 27231, Python] Why I'm Looking Forward to 2023

Problem link

boj 27231

Classification

Brute Force Algorithms, Backtracking

Description

It's nice to see that I've been able to solve problems that I couldn't solve before, so it feels good to know that I've improved.

In the case of this problem, my last attempt was submitted to the competition 5 months ago, but I've written down the solution several times in the meantime.

The reason why there are multiple attempts is because there is only one condition missing, but I'm still not sure why I get a timeout for missing this condition. I hope it's a reason that I can make up later. → I thought of this while organizing the content below. Organizing your blog is the best!

Let me introduce the problem-solving approach

Bitmask the coordinates between the * + symbols to check for whole numbers

• Set or sort in a list that doesn't allow duplicates

• Counting numbers up to the number initially entered (because no matter how you slice it, it can never be larger than that number) with increasing squared size

And here's where we run into a problem.

For a number consisting of 0s and 1s, I should output Hello, BOJ 2023!, because if you break it down to a single number, the value will remain unchanged no matter how many times you square it, but I was simply excluding the case of 1.

To check this part, I was able to handle the edge case by checking for a single number greater than 2 and printing Hello, BOJ 2023! if there is no term greater than 2, which is the correct answer.

Solving code

# 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)