[BOJ/백준] 7490 0 만들기 파이썬

문제 링크 : https://www.acmicpc.net/problem/7490

7490번: 0 만들기

 

백트래킹, 브루트포스 문제이다.

1~N까지 숫자들 사이에 연산자 '+','-',' ' 중 한가지를 반드시 넣고 결과를 계산해서 그 값이 0인 것의 식을 출력하는 것이다.

' '의 경우 두수를 붙이는 것이다.

 

연산자들을 모두 넣고 마지막에 계산해야한다.

중간중간에 계산한다면 더 복잡해질 것이다. 1-2 3 같은 경우가 힘들듯하다.

그래서 모든 자리에 다 연산자를 넣고 마지막에 값만 계산해서 확인하면 된다.

 

연산자 넣는 것은 간단한 백트래킹, 재귀로 구현이 가능하다.

 

모든 연산자를 넣은 값 후 계산의 경우 eval() 메서드를 이용하면 아주 쉽다.

그게 아니면 for문으로 검사해도 쉽게 할 수 있다.

 

eval()은 문자열로 된 식을 계산해주는 파이썬 내장함수이다.

eval('1+2'), eval('abs(-1)') 이런 문자열로 된 식을 계산해준다.

그렇기 때문에 백트래킹으로 다 정하고 마지막에 eval로 계산해주면 된다. 

 

값을 계산할때는 ' ' 문자를 ''으로 바꿔야 정확한 식이 되는 것이니 주의하자

 

마지막 출력할 때 아스키 코드 순으로 출력하라 했다.

숫자야 그 순서대로 아스키코드 순이지만 ' ','+','-'는 다르다

그래서 중간중간 결과값을 배열에 저장후 정렬해도 되지만 백트래킹 시 우선순위에 따라 넣고 출력해주면 된다.

연산자의 우선순위는 ' ','+' ,'-' 순이다. 이를 배열에 넣고 정렬해서 확인 가능하다.

tc = int(input())

def solv():
    global n,answer
    n = int(input())
    answer = []
    select_operator(2,'1')
    print()
def select_operator(now,ans):
    global answer
    if now == n+1:
        calc(ans)
        return

    select_operator(now+1,ans+' '+str(now))
    select_operator(now+1,ans+'+'+str(now))
    select_operator(now+1,ans+'-'+str(now))

def calc(ans):
    tmp = ans.replace(' ','')
    if eval(tmp) == 0:
        print(ans)
for _ in range(tc):
    solv()