[BOJ 7490, Python] 0 만들기

문제 링크

BOJ 7490

분류

백트래킹, 브루트포스 알고리즘, 구현, 문자열

설명

전형적인 백트래킹 문제라고 생각한다. 하지만 처리 과정이 살짝 난해한 점이 있었고 정렬 방식이 ASCII 순이라는 것도 조금 특이했던 것 같다.

Python의 Eval 함수를 사용하면 쉽게 해결할 수 있다고 봤는데 해당 방식을 사용하지 않고 정공법으로 해결하였다.

기본적으로 숫자의 합과 기존에 미처리된 숫자 2개를 들고 백트래킹을 진행하면서 '덧셈', '뺄셈', '연산하지 않음' 이 3가지 케이스에 대해서 전부 확인해준다는 생각으로 시도했고 맞았습니다를 받을 수 있었다.

풀이 코드

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