[백준] 7490 "0 만들기" -python

 

알고리즘

 N개의 숫자에 대해 N-1번 연산을 수행하면서 각 연산에서는 공백, 덧셈, 뺄셈을 수행 가능하므로 재귀를 통해 연산자를 넘겨주면서 빽트래킹 알고리즘을 이용한다. 3^(N-1) 만큼의 시간이 걸리지만 N의 최대값 자체가 9이므로 백트래킹을 통해 효율적으로 구현 가능하다. 또한, 수식 연산시 파이썬의 내장함수인 eval()을 이용하였다. eval()함수는 파라미터로 수식을 str타입으로 전달해주게 되면 계산해주는 착한 친구이다.  

 

소스코드

# 0 만들기
n = int(input())

def func(k, r: str, N): #반복, 수식, 값
    if k == N+1:
        result = eval(r.replace(" ", ""))
        if result == 0:
            print(r)
        return
    
    func(k+1, f'{r}{" "}{k}', N)
    func(k+1, f'{r}{"+"}{k}', N)
    func(k+1, f'{r}{"-"}{k}', N)
    
for i in range(n):
    N = int(input())
    func(2, "1", N)
    if i != n-1: 
        print()

 

느낀점

 백트래킹을 수행할 때 공백, 덧셈, 뺄셈 순서대로 탐색하지 않으면 정답 처리가 안되니 주의해야 한다.