[백준] 0 만들기
재귀
백준
medium
문제
1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 … N을 생각하자.
그리고 ‘+’나 ‘-‘, 또는 ‘ ‘(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.
N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.
입력
첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).
각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).
2
3
7
출력
각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.
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
재귀를 이용한 경우의 수 조합
N=3일 때, +, -, ` ` 세 개의 연산자로 수행할 수 있는 연산 조합은 3^N-1 이다.
그리고 3 <= N <= 9이기 때문에, 완전탐색으로 모든 조합을 구해서 문제를 풀 수 있다.
조합의 경우의 수를 모두 찾기 위해 재귀를 사용한다.
def recursive(array, n):
if len(array) == n:
operator_list.append(copy.deepcopy(array))
return
array.append(' ')
recursive(array, n)
array.pop()
array.append('+')
recursive(array, n)
array.pop()
array.append('-')
recursive(array, n)
array.pop()