[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 7490번 _ 0 만들기

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

7490번: 0 만들기

[문제]

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

 

[입력]

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

[출력]

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

 

[아이디어]

1) 가능한 모든 연산의 경우의 수를 구해놓고, 계산 결과가 0인 것들만 남긴 후 정렬한다.

2) 1)을 수행할 때 eval 함수를 활용할 수 있다.

 

def zero(n):
    ans = ['']
    for i in range(1,n+1):
        for _ in range(len(ans)):
            tmp = ans.pop(0)
            tmp+= str(i)
            if i==n:
                ans.append(tmp)
            else:
                for x in ["+", "-", " "]:
                    ans.append(tmp + x)
    ans = [x for x in ans if eval(x.replace(" ", ""))==0]
    return sorted(ans)

for k in range(int(input())):
    print(*zero(int(input())), sep='\n')
    print()

아래처럼 재귀를 활용한 풀이도 있었다.

def zero(s, n):
    if n > N:
        if eval(s.replace(" ", "")) == 0:
            print(s)
    else:
        zero(f"{s} {n}", n + 1)
        zero(f"{s}+{n}", n + 1)
        zero(f"{s}-{n}", n + 1)


for _ in range(int(input())):
    N = int(input())
    zero("1", 2)
    print()