[BOJ 7490, Python] Create 0

Problem link

boj 7490

Classification

Backtracking, Brute Force Algorithms, Implementations, Strings

Description

I think this is a classic backtracking problem. However, I found the processing a bit esoteric and the ASCII sorting a bit unusual.

I saw that it could be easily solved using Python's Eval function, but I didn't use that approach and solved it the hard way.

Basically, I took the sum of a number and two previously unprocessed numbers and backtracked, thinking that it would check for all three cases of 'addition', 'subtraction', and 'no operation', and I was able to get the correct answer.

Solved code.

# 0 만들기

import sys

input = sys.stdin.readline

def make_sum_zero(
    result_arr: set,
    target_arr: list,
    last_index: int,
    now_index: int = 0,
    sum_now: int = 0,
    now_calc: int = 0,
    log=[],
) -> None:
    """
    백트래킹을 활용하여 숫자들의 합이 0이 되도록 만드는 함수
    """
    if last_index == now_index:
        if not sum_now + now_calc:
            result_arr.add("".join(log))

    else:
        if not now_index:
            make_sum_zero(
                result_arr,
                target_arr,
                last_index,
                now_index + 1,
                0,
                target_arr[now_index],
                [str(target_arr[now_index])],
            )

        else:
            new_number = target_arr[now_index]

            make_sum_zero(
                result_arr,
                target_arr,
                last_index,
                now_index + 1,
                sum_now + now_calc,
                new_number,
                log + ["+", str(new_number)],
            )
            make_sum_zero(
                result_arr,
                target_arr,
                last_index,
                now_index + 1,
                sum_now + now_calc,
                -new_number,
                log + ["-", str(new_number)],
            )

            if now_calc < 0:
                make_sum_zero(
                    result_arr,
                    target_arr,
                    last_index,
                    now_index + 1,
                    sum_now,
                    10 * now_calc - new_number,
                    log + [" ", str(new_number)],
                )
            else:
                make_sum_zero(
                    result_arr,
                    target_arr,
                    last_index,
                    now_index + 1,
                    sum_now,
                    10 * now_calc + new_number,
                    log + [" ", str(new_number)],
                )

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

for _ in range(testcase):
    arr_length = int(input())
    result = set()

    # 함수를 통해 결과 확인
    target_arr = [i for i in range(1, arr_length + 1)]
    make_sum_zero(result, target_arr, arr_length)

    # 혹여라도 겹치는 결과가 있다면 Set을 통해 배제, ASCII 순으로 정렬
    sort_result = sorted(list(result), key=lambda x: ascii(x))
    output.append(sort_result)

# 문제 조건에 맞춰 출력
for idx in range(testcase):
    for element_idx in range(len(output[idx])):
        print(output[idx][element_idx])

    if idx != testcase - 1:
        print("")