[Problem Solving] BOJ 7490: 0 만들기

문제 링크: https://www.acmicpc.net/problem/7490

 

백트래킹 + 문자열 문제이다. 

1부터 N까지의 수를 순서대로 늘어놓고 인접한 수를 붙이거나 더하거나 빼서 0이 되는 경우의 수를 출력하는 문제이다.

백트래킹이기 때문에 모든 함수를 재귀 호출하여 모든 경우의 수를 따져본다.

식을 s에 만들어서 재귀함수에 넘겨준다. 공백이 있으면 replace함수로 공백을 제거한다음에 eval(e)로 0이면 s를 출력한다.

 

import sys
sys.setrecursionlimit(10 ** 6)
read = sys.stdin.readline

N = 0
def is_zero(s):
    e = s.replace(" ", "").rstrip()
    if eval(e) == 0:
        return True
    return False

def dfs(i, s):
    if i == N:
        if is_zero(s):
            print(s)
    else:
        dfs(i + 1, s + " " + str(i + 1))
        dfs(i + 1, s + "+" + str(i + 1))
        dfs(i + 1, s + "-" + str(i + 1))

T = int(read())
for _ in range(T):
    N = int(read())
    dfs(1, "1")
    print()