[백준] 7490. 0 만들기(python, 파이썬)

문제

7490. 0 만들기

📌 아이디어

이 문제는 브루트포스 알고리즘을 적용하여 모든 경우의 수식을 만들어 0이 되는 경우를 도출하면 간단하게 해결할 수 있습니다.

1. DFS 함수를 만들어 3가지 경우를 탐색합니다.
2. 공백, 덧셈, 뺄셈 순으로 재귀를 진행합니다.
3. 현재 숫자가 N이라면 탐색을 종료하고 연산을 진행합니다.
4. 연산 결과가 0인 경우 정답 리스트에 추가 후 정답을 출력합니다.

연산은 파이썬 내장 함수인 eval을 사용했습니다.
→ eval 함수는 문자열로 표현된 파이썬 표현식(expression)이나 문장(statement)을 인수로 받고, 해당 코드를 실행하여 결과를 반환합니다.

📌 코드

import sys
input = sys.stdin.readline

def dfs(n, idx, rst):
    if idx == N:
        # eval 함수를 활용하여 문자열 상태에서 연산이 가능하도록
        ans = eval(rst.replace(' ', ''))
        # 연산 결과가 0이면 정답 리스트에 추가
        if ans == 0:
            ans_sik.append(rst)
        return
    else:
        n_idx = idx + 1
        # 공백인 경우 숫자를 이어붙이기
        dfs(n, n_idx, rst + ' ' + str(n_idx))
        # +인 경우 더하기
        dfs(n, n_idx, rst + '+' + str(n_idx))
        # -인 경우 빼기
        dfs(n, n_idx, rst + '-' + str(n_idx))

T = int(input())
for _ in range(T):
    N = int(input())
    ans_sik = []
    dfs(N, 1, '1')
    for a in ans_sik:
        print(a)
    print()

피드백 및 개선점은 댓글을 통해 알려주세요😊