[python] 백준 7490 0 만들기

https://www.acmicpc.net/problem/7490

7490번: 0 만들기

 

문제 해결

• 처음 보았을 때 많이 당황스러운 문제였다.
• 1부터 N까지 덧셈, 뺄셈, 이어붙이기로 각각 계산
• 따라서 1부터 시작하여 +, -, 이어 붙이기 중 한 가지를 선택한 후 다음 수 2를 붙인다.
• 이와 같은 일을 N번 반복하므로 재귀를 이용하여 풀 생각을 한다.
• 필요한 변수는
  • sum: 1부터 n-1까지 합 (후에 1부터 N까지 합이 0이 되었을 때만 확인하면 되므로)
  • sign: 1이면 덧셈, -1이면 뺄셈, sign 그대로이면 이어 붙이기로 판별
  • num: 현재 만들고 있는 숫자
  • n : n번째 확인
  • string: 현재까지 만든 식

CODE

def recur(sum, sign, num, n, string):
  if (n == N):
    sum = sum + (sign*num)
    if sum == 0:
      print(string)
  else:
    recur(sum         ,sign , num*10+(n+1), n+1, string+' '+str(n+1))
    recur(sum+sign*num,1    , (n+1)       , n+1, string+'+'+str(n+1))
    recur(sum+sign*num,-1   , (n+1)       , n+1, string+'-'+str(n+1))

if __name__=='__main__':
    t = int(input())
    for _ in range(t):
      N = int(input())
      recur(0,1,1,1,"1")
      print()