[백준 7490 🥇] 0 만들기

문제

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

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

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

입력

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

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

출력

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

문제풀이

import sys

t=int(sys.stdin.readline())

def calculate(express):
    if ' ' in express:
        express=express.replace(' ','')
    return eval(express)

def combination(num, arr):
    global n, ans
    if num==n:
        if calculate(arr)==0:
            ans.append(arr)
        return
    combination(num+1, arr+'+'+str(num+1))
    combination(num+1, arr+'-'+str(num+1))
    combination(num+1, arr+' '+str(num+1))

for _ in range(t):
    n=int(sys.stdin.readline())
    ans=[]
    combination(1, '1')
    ans.sort()
    for a in ans:
        print(a)
    print('')

• 재귀함수를 이용해서 n을 입력받아서 만들어낼 수 있는 모든 수식들을 탐색한다.
• 재귀함수 combination에서 추가하거나, 빼거나, 이어주는 숫자 num이 n이라면 즉, arr가 1부터 n까지 포함하는 문자열이라면 calculate 함수를 이용해서 해당 수식의 값이 0인지 확인한다.
• 0이라면 배열 ans에 추가해준다.
• calculate 함수에선 먼저 수식의 공백을 replace를 이용해서 제거해준다.
• 여기서 replace는 sort함수처럼 리턴값 없이 직접적으로 해당 문자열에 변환을 주는 것이 아니라, 반환 값을 주는 것이므로 express=express.replace(' ','')의 반환값을 express에 대입해줘야 정상적으로 계산된다.
• 공백이 제거된 express를 문자열 수식을 계산해주는 파이썬 내장함수 eval()을 이용해서 계산한다.
• 마지막으로 ans에 저장된 문자열들을 아스키 코드순으로 정렬해준 뒤에 출력해준다.