[백준][Python] 7490 0 만들기

구현, 문자열, 브루트포스, 백트래킹 / 골드 5

🧮

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

7490번: 0 만들기

 

 

내 풀이

def dfs(n, s):
    if n == N:
        s += str(N)
        ns = ''.join(s.split())
        if eval(ns) == 0:
            ans.append(s)
        return
    
    dfs(n+1, s + str(n) + '+')
    dfs(n+1, s + str(n) + '-')
    dfs(n+1, s + str(n) + ' ')

T = int(input())

for _ in range(T):
    ans = []
    N = int(input())

    dfs(1, '') # 현재 숫자, 수식

    print(*sorted(ans), sep='\n')
    print()

 

 

코드 설명

 

✔️ dfs 함수

 

dfs를 호출할 때, 매개변수로는 현재 숫자와 수식을 넘겨준다.

 

n == N이면, 마지막 숫자를 수식에 추가해 준 뒤, 수식을 공백 기준으로 자른 후, ''.join으로 최종 수식을 만들어줬다.

이렇게 처리한 이유는, eval함수에서 문자열 중간에 공백이 있으면 에러가 발생하기 때문이다.

수식의 값이 0이라면, 정답 리스트에 추가한다.

이때, 공백을 없애기 전인 기존 문자열(원본) s를 추가해주어야 한다.

if n == N:
    s += str(N)
    ns = ''.join(s.split())
    if eval(ns) == 0:
        ans.append(s)
    return

 

백트래킹, 브루트포스로 풀었다.

현재 숫자 뒤에 올 수 있는 문자는 +, -, 공백 이렇게 3개다.

가능한 모든 경우의 수를 검사한다.

dfs(n+1, s + str(n) + '+')
dfs(n+1, s + str(n) + '-')
dfs(n+1, s + str(n) + ' ')