0 만들기 - 7490

Published on November 09, 2021 by Hyle

재귀

2 min READ

0 만들기

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 … N을 생각하자.

그리고 ‘+’나 ‘-‘, 또는 ‘ ‘(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

예제 입력 1

2 3 7

예제 출력 1

1+2-3

1+2-3+4-5-6+7 1+2-3-4+5+6-7 1-2 3+4+5+6+7 1-2 3-4 5+6 7 1-2+3+4-5+6-7 1-2-3-4-5+6+7 출

On my way

def recursive(array, n):
    if len(array) == n:
        operators_list.append(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 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()

💡 수의 범위가 적으므로 완전탐색으로 풀 수 있다. 수 리스트/연산자 리스트로 나누어 생각하자 연산자는 총 n-1개 들어갈 수 있으며 연산자리스트의 종류는 3**(n-1)가지 이다.

💡 eval()함수를 이용하여 문자열을 계산할 수 있다.