[알고리즘] 숫자 만들기

포인트

• 재귀를 잘 사용을 할 수 있는가?  생각해 볼 수 있는 문제입니다. 생각보다 이 문제를 풀면 이해하기가 쉽습니다. 이런 패턴도 잘 익히시면 좋을 것 같습니다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

import sys

sys.stdin = open('input.txt')


def go(index: int, total: int, plus: int, minus: int, multiple: int, divide: int) -> None:
	global max_result, min_result
	
	if not plus and not minus and not multiple and not divide:
		max_result = max(max_result, total)
		min_result = min(min_result, total)
		return
	
	if plus:
		go(index + 1, total + data[index], plus - 1, minus, multiple, divide)
	# 플러스를 제일 먼저 다 지운다.
	
	if minus:
		go(index + 1, total - data[index], plus, minus - 1, multiple, divide)
	# 마이너스를 제일 먼저 다 지운다.
	
	if multiple:
		go(index + 1, total * data[index], plus, minus, multiple - 1, divide)
	# 곱셈을 제일 먼저 다 지운다.
	
	if divide:
		go(index + 1, int(total / data[index]), plus, minus, multiple, divide - 1)


# 나눗셈을 제일 먼저 다 지운다.


for test in range(1, int(input()) + 1):
	n = int(input())
	plus, minus, multiple, divide = map(int, input().split())
	data = list(map(int, input().split()))
	max_result = -987654321
	min_result = 987654321
	go(1, data[0], plus, minus, multiple, divide)
	print('#{} {}'.format(test, abs(max_result - min_result)))