[백준] 2579번: 계단 오르기

스스로 푼 문제: O
걸린 시간: 15분

문제

풀이

자연수 N의 범위가 3 <= N <= 9여서 각 숫자 사이에 ' ', '+', '-' 을 넣는 모든 경우의 수를 해보아도 $3^8$이어서 모든 경우의 수를 시도해도 시간 내에 가능하다고 생각해 백트래킹으로 풀이를 했다.

코드

t = int(input())

def back_tracking(n, num, equation):
  # 종료 조건
  if num == n:
    equation += [str(num)]
    result = eval((''.join(equation)).replace(' ',''))
    if result == 0:
      print(*equation, sep='')
    return

  for operator in [' ', '+', '-']:
    back_tracking(n, num+1, equation+[str(num)]+[operator])

for i in range(t):
  n = int(input())
  back_tracking(n, 1, [])

  if i != t-1:
    print('')