[알고리즘] 백준 - 0 만들기

백준 - 0 만들기

내 풀이

T = int(input())

opr = [" ", "+", "-"]


# 아스키 코드 순서 " ", "+", "-"
def back_tracking(nums, cur_equation, cur_index):
    if cur_index == len(nums) - 1:  # 맨 마지막 숫자에는 opr 안붙인다
        cur_equation += str(nums[cur_index])
        clean_equation = cur_equation.replace(" ", "")

        if eval(clean_equation) == 0:
            print(cur_equation)
        return

    for i in range(3):
        back_tracking(nums, cur_equation + str(nums[cur_index]) + opr[i], cur_index + 1)


for _ in range(T):
    N = int(input())
    nums = [i for i in range(1, N + 1)]
    back_tracking(nums, "", 0)
    print()

정확히 말하면 backtracking은 아니고 부르트포스다. 아쉬운 부분은 eval()을 썼다는 점과, 아스키 코드를 찾아봤다는 점이다. 그냥 opr을 정렬하면 알아서 아스키 코드로 적용할 수 있었다. eval()을 안쓰고 푸는 방법도 찾아보자.

다른 사람 풀이

def make_zero(cur_sum, sign, num, cur_index, number_str): # num이란 이전의 값이다 
    global last_number
    if cur_index == last_number:
        cur_sum += (num * sign)
        if cur_sum == 0:
            print(number_str)
        return

    #  '+'나 '-'를 만나면 이전의 값(num)을 sum에 더해주거나 빼준다. 그전에는 sum에 아무런 계산을 하지 않는다.
    make_zero(cur_sum, sign, num * 10 + (cur_index + 1), cur_index + 1, number_str + " " + str(cur_index + 1))
    make_zero(cur_sum + (sign * num), 1, cur_index + 1, cur_index + 1, number_str + "+" + str(cur_index + 1)) 
    make_zero(cur_sum + (sign * num), -1, cur_index + 1, cur_index + 1, number_str + "-" + str(cur_index + 1))


T = int(input())
last_number = 0
for i in range(T):
    last_number = int(input())
    number_str = "1"
    make_zero(0, 1, 1, 1, number_str)
    print()