[BOJ/백준] 7490번 0 만들기 (Python 파이썬)

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

7490번: 0 만들기

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	4368	2064	1532	46.396%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1 

2
3
7

예제 출력 1 

1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

 

---

풀이

이전에 풀이했던 "연산자 끼워넣기" 문제와 유사한 문제입니다. 1부터 시작하는 수열에 +나 -를 삽입하면 됩니다.

https://great-park.tistory.com/42

[BOJ/백준] 14888번 연산자 끼워넣기 (Python 파이썬)

다만, 이번에는 ASCII 순서에 따라서 연산식을 출력해야 합니다. 따라서 공백, 더하기, 빼기 순으로 우선 순위를 둡니다.
이때, eval()을 사용해서 문자열로 구성된 연산식으로 실제 연산을 수행할 수 있습니다.
이를 이용하여 종결 조건과 출력을 연결지으면 다음과 같습니다.

def set_ans(ans):
    if eval(ans) == 0:
        print(ans)

 

이제 set_ans를 언제 호출할까요? 문자열로 연산식을 만들어가는 과정을 생각하면, 항상 오른쪽 끝에는 숫자가 와야 합니다. 즉, 다음 숫자를 추가하였을 때, 연산식의 길이를 체크해서 set_ans를 호출해야 합니다.
여기서 N은 3이상입니다. 따라서 연산식에는 무조건 1,2,3이 포함될 겁니다. 변수가 생기는 지점은 1 다음의 연산자 자리부터 입니다. 따라서 다음과 같이 작성합니다.

def select_operator(depth, ans):
    global answer
    if depth == N+1:
        set_ans(ans)
        return
    # 아스키코드 순으로 호출
    select_operator(depth+1, ans+' '+str(depth))
    select_operator(depth+1, ans+'+'+str(depth))
    select_operator(depth+1, ans+'-'+str(depth))
    
    
    
select_operator(2, '1')

위와 같이 작성하면, 일단 "1"은 고정이고, 다음에 올 연산자와 "2"가 각 경우마다 연산식에 추가됩니다.

이때, select_operator를 위처럼 아스키코드 순으로 호출하게 되면 결국은 같은 depth내에서 연산자 3개에 대한 경우를 모두 호출했기 때문에 빠짐없이 검토할 수 있습니다. 
어짜피 depth가 초과하게 되면 호출 후 함수에서 return하기 때문에 정확히 backtrack이 구현되는 것이죠
해당 함수가 재귀적으로 호출될 때마다 tree 구조에서 가지가 하나씩 뻗는다고 생각하면 쉽습니다.

최종 코드

import sys
input = sys.stdin.readline

test_case = int(input())


def solve():
    global N, answer
    N = int(input())
    answer = []
    select_operator(2, '1')
    print()


def select_operator(depth, ans):
    global answer
    if depth == N+1:
        set_ans(ans)
        return
    # 아스키코드 순으로 호출
    select_operator(depth+1, ans+' '+str(depth))
    select_operator(depth+1, ans+'+'+str(depth))
    select_operator(depth+1, ans+'-'+str(depth))


def set_ans(ans):
    cal_ans = ans.replace(' ', '')
    if eval(cal_ans) == 0:
        print(ans)


for _ in range(test_case):
    solve()