백준 7490번: 0만들기(BFS, 재귀함수)

문제

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

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

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

입력

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

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

출력

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

문제설명:

이 문제는 1~N까지의 수를 오름차순으로 나열하여 각 숫자 사이에 '+', '-', ' ',을 넣은 최종적으로 완료된 수식의 합이 0이 되는 수식을 구하는 문제입니다.

문제를 해결하기위해서 숫자만 있는 리스트와 연산자 리스트를 분리하여 모든 경우의 수를 계산하기 위하여

리스트를 재귀함수를 통해서 만들 수 있는 각 연산자 리스트를 n-1개의 길이만큼 만듭니다.

그 후 문자열에 수의 리스트값과 연산자 리스트 값을 더하여 파이썬의 eval()함수를 통하여 문자열 형태의 수식의 합이 0인 경우만 출력을 합니다.

아래 코드입니다.

import copy

# 수의 리스트와 연산자 리스트를 분리하여 모든 경우의 수를 계산한다.
# 연산자 리스트는 항상 n-1개의 연산자가 들어가기때문에 총 3의 (n-1)승 가지가 존재한다.
# 가능한 모든 경우를 고려하여 연산자 리스트를 만드는 것이 관건 (재귀함수 이용)
# 파이썬의 eval()함수를 이용하여 문자열 형태의 표현식을 계산할 수 있습니다.
T = int(input())  # 테스트 케이스


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

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

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


for i in range(T):
    operate_list = []
    n = int(input())
    solve([], n - 1)

    num_list = []
    for j in range(1, n + 1):
        num_list.append(j)

    for op in operate_list:
        result = ""
        for k in range(n - 1):  # 연산자는 n-1개 있으므로
            result += str(num_list[k]) + op[k]
        result += str(num_list[-1])  # 숫자 리스트의 마지막을 더해준다
        if eval(result.replace(" ", "")) == 0:  # 공백을 없애서 붙인 숫자로 표현
            print(result)
    print()

 

사용언어: python

문제출처: www.acmicpc.net/problem/7490

7490번: 0 만들기