백준 7490 : 문제링크

  • 문제유형 : 재귀

  • 설명

    1. 자연수 N의 범위(3 <= N <= 9)가 한정적이므로 완전 탐색으로 문제 해결

    2. 수의 리스트와 연산자의 리스트로 분리하여 모든 경우의 수를 해결

    3. 가능한 모든 경우를 고려하여 연산자 리스트를 만들 때 재귀를 사용

    4. 파이썬 eval() 함수를 이용하여 문자열 형태의 표현식을 계산한다.

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    import copy

    def recursion(array, n):
        if len(array) == n:
            operators_list.append(copy.deepcopy(array))
            return
        array.append(' ')
        resursive(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 operators in operators_list:
            string = ""
            for i in range(n-1):
                string += str(integers[i]) + operators[i]
            string += str(integers[-1])
            if eval(string.replace(" ", "")) == 0:
                print(string)
        print()