14888. 연산자 끼워넣기

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

 

import sys

'''
chosen 리스트에 담긴 순서대로 계산하는 함수
0: +, 1: -, 2: *, 3: / 로,
chosen에 0, 0, 1, 2, 3이 담겨있다면 연산자 순서는 + + - * / 이 된다.
그리고 numbers와 chosen에서 하나씩 꺼내오면서 계산 후 결과를 리턴 
'''
def calc():
    ret = numbers[0]  # 일단 첫번째 숫자를 결과에 넣고 시작
    for idx, op in enumerate(chosen):
        if op == 0:
            ret += numbers[idx+1]
        elif op == 1:
            ret -= numbers[idx+1]
        elif op == 2:
            ret *= numbers[idx+1]
        else:
            if ret < 0:
                ret = -(abs(ret) // numbers[idx+1])  # 문제에 있던 c++14 스타일 음수 나눗셈
            else:
                ret = ret // numbers[idx+1]
    return ret


'''
연산자의 종류는 총 4개이므로, 4번을 for문으로 돌되 
선택된 연산자는 oper 리스트에서 1씩 빼 준다. 0이 되면 그 연산자를 패스한다.
순열과 똑같다.
'''
def dfs(count):
    global minValue, maxValue
    if count == sum:
        minValue = min(minValue, calc())
        maxValue = max(maxValue, calc())
        return
    for i in range(4):
        if oper[i] <= 0:
            continue
        oper[i] -= 1
        chosen.append(i)  # 0-더하기,1-빼기,2-곱,3-나누기
        dfs(count+1)
        chosen.pop()
        oper[i] += 1


n = int(sys.stdin.readline()) # 숫자의 갯수. 문제에서의 n
numbers = list(map(int, sys.stdin.readline().split()))  # 숫자 리스트
oper = list(map(int, sys.stdin.readline().split()))  # 입력 받는 연산자 배열. ex) 0 1 0 0
sum = 0  # 입력 받은 oper 리스트의 합. 이제 연산자 선택을 다 했으니 계산해라~할 때 조건문에 쓰임
for i in oper:
    sum += i
chosen = []  # 선택된 연산자
ret = 0  # 각 케이스 별 계산 결과를 담을 변수
minValue = 1000000000  # 주의! 0으로 초기화하면 min이 0이 되어버릴 수 있음
maxValue = -1000000000
dfs(0)
print(maxValue)
print(minValue)