[백준/python] 7490번 : 0 만들기

문제

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

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

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

 

입력

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

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

 

출력

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

 

정답

from itertools import product
import sys
input = sys.stdin.readline

answer = []
for _ in range(int(input())):
    N = int(input())
    
    result = []
    for insert in product(['+', '-', ' '], repeat=N-1):
        num = 1
        expression = '1'
        for i in insert:
            num += 1
            expression += i + str(num)
        
        if eval(expression.replace(' ', '')) == 0:
            result.append(expression)

    answer.append(sorted(result))

for result in answer:
    for r in result:
        print(r)
    print()

---

모든 경우의 수를 다 검사하는 브루트포스 알고리즘을 활용한다.

 

중복 순열 product를 이용하여 +, -, 띄어쓰기 중 중복을 허용하여 N-1개를 뽑는다.

이후 expression에 숫자와 번갈아 넣으며 수식 문자열을 완성한다.

 

expression의 공백을 제거하고 eval을 이용하여 계산했을 때 값이 0이라면 result에 넣는다.

result를 정렬하여 answer에 넣고 출력 형식에 맞춰 출력한다.

 

2021.04.01 - [🔍알고리즘/🔅개념정리] - [파이썬/python] 순열과 조합 : itertools 이용하기 (permutations, combinations)

[파이썬/python] 순열과 조합 : itertools 이용하기 (permutations, combinations)