파이썬) 0 만들기 - BOJ

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

7490번: 0 만들기

구현 + dfs + 브루트포스 문제인거같다. 

처음 제출한 코드는 다음과 같다

t = int(input())

result = []


def dfs(arr, current_idx, n, s, condition, num):
    if current_idx == n:
        new_s = s.replace(' ', '')

        if eval(new_s) == 0:
            if s not in result:
                result.append(s)3
        return

    if condition == 'plus':
        s = s + '+' + str(arr[current_idx])
    elif condition == 'minus':
        s = s + '-' + str(arr[current_idx])
    else:
        s = s + ' ' + str(arr[current_idx])

    current_idx += 1

    dfs(arr, current_idx, n, s, 'plus', num)
    dfs(arr, current_idx, n, s, 'minus', num)
    dfs(arr, current_idx, n, s, 'space', num)


for _ in range(t):
    n = int(input())
    result = []

    arr = [i+1 for i in range(n)]

    dfs(arr, 1, n, '1', 'plus', 1)
    dfs(arr, 1, n, '1', 'minus', 1)
    dfs(arr, 1, n, '1', 'space', 1)
    result.sort()
    print(result)

 

그러나 25퍼센트 쯤에서 틀려버렸다.

테스트 케이스가 부족해 무엇이 문제인지 몰라 결국 다시 코드를 작성하기 시작했다.

 

t = int(input())

result = []


def dfs(n, s, num):
    if num == n:
        # 탈출조건
        if eval(s.replace(' ', '')) == 0:
            # eval로 스트링 계산을 함

            return print(s)
        return
    num += 1

    dfs(n, s+' '+str(num), num)
    # 각각 플러스 마이너스 스페이싱을 해야한다.
    dfs(n, s+'+'+str(num), num)
    dfs(n, s+'-'+str(num), num)


for _ in range(t):
    n = int(input())

    dfs(n, '1', 1)
    print()