백준 7490 0 만들기

과정

• 백트래킹을 통해 기호들로 만들어진 배열을 만든다.
  • 순서와 반복 여부는 따지지 않는다.
• 전체 배열을 만든 후에 값을 계산한다.
  • 인덱스에 주의해서 계산한다.
  • • 인 경우는 그냥 값을 더하고, - 인 경우는 그냥 값을 빼면 된다.
  • 띄어쓰기가 들어온 경우가 힘들었다.
    • 이전의 기호가 + 면, 이전 값을 - 해준 다음, *10하고, 현재 값을 더한다.
    • 이전의 기호가 - 면, 이전 값을 + 해준 다음, *10하고, 현재 값을 더한다.
    • 단순히 이전 계산 과정을 하기 전 상태로 돌리고 계산한 것이다.
• 만일 입력 값이 더 큰 수가 들어와서 띄어쓰기가 여러 번 되는 경우는 반례가 될 수 있다.
  • 그러나 입력으로 9 이하의 수가 들어온다고 했으니, 띄어쓰기가 두 번 이상 되는 경우는 존재하지 않는다.

tc = int(input())

def main(level, now):
    if level == N - 1:
        ans = 1
        for i in range(N - 1):
            if now[i] == "+":
                ans += lst[i]
            elif now[i] == "-":
                ans -= lst[i]
            elif now[i] == " ":
                if i < 1:
                    ans = ans * 10 + lst[i]
                elif now[i - 1] == "+":
                    ans = (ans - lst[i - 1]) + (lst[i - 1] * 10 + lst[i])
                elif now[i - 1] == "-":
                    ans = (ans + lst[i - 1]) - (lst[i - 1] * 10 + lst[i])

        if ans == 0:
            print(1, end="")
            for i in range(N - 1):
                print(now[i], end="")
                print(lst[i], end="")
            print()
        return
    
    for i in [" ", "+", "-"]:
        if level > 0 and (now[-1] == " " and i == " "):
            continue
        else:
            now += i
            main(level + 1, now)
        now = now[:-1]

for _ in range(tc):
    N = int(input())
    lst = [i for i in range(2, N + 1)]
    main(0, "")
    print()