백준#7490 0만들기

문제

https://www.acmicpc.net/problem/7490

풀이

나의 풀이

• 재귀를 사용해서 풀진 못했다
• 

case_num = int(input())


def get_formulas(num: int):
    formulas = ['', '', '']
    for n in range(1, num+1):
        new_formulas = []
        for formula in formulas:
            if n == num:
                new_formulas.append(formula + str(n))
            else:
                for cal in ['+', '-', ' ']:
                    new_formulas.append(formula+str(n)+cal)
        formulas = new_formulas
    return sorted(list(set(formulas)))


def cal_formula(formula: str):
    new_formula = formula.replace(' ', '')
    result = eval(new_formula)
    return result


def find_zero_index(formulas):
    result = []
    for index, f in enumerate(formulas):
        if cal_formula(f) == 0:
            result.append(index)
    return result


for _ in range(case_num):
    num = int(input())
    formulas = get_formulas(num)
    indexes = find_zero_index(formulas)
    for index in indexes:
        print(formulas[index])
    print()

다른 사람의 풀이

• 자연수 N의 범위(3<=N<=9)가 매우 한정적이므로, 완전탐색으로 문제를 해결할 수 있음
• 수의 리스트와 연산자 리스트를 분리하여 모든 경우의 수를 계산
• 가능한 모든 경우를 고려하여 연산자 리스트를 만드는 것이 관건 (재귀 함수 이용)
• 파이썬의 eval()함수를 이용하여 문자열 형태의 표현식을 계산할 수 있음
  

import copy


def recursive(array, n):
    if len(array) == n:
        operators_list.append(copy.deepcopy(array))
        return
    array.append(' ')
    recursive(array, n)
    array.pop()

    array.append('+')
    recursive(array, n)
    array.pop()

    array.append('-')
    recursive(array, n)
    array.pop()


test_case = int(input())

for _ in range(test_case):
    operators_list = []
    n = int(input())
    recursive([], n-1)
    integers = [i for i in range(1, n+1)]

    for operator in operators_list:
        string = ""
        for i in range(n-1):
            string += str(integers[i]) + operator[i]
        string += str(integers[-1])
        if eval(string.replace(" ", "")) == 0:
            print(string)
    print()

느낀점