[SWEA] 4008 : 보호필름 - Python

N개의 숫자, 연산자 4개
왼쪽에서부터 차례대로 계산
계산한 결과 최대 최소 차이

내 코드

import sys
sys.stdin = open("input.txt", "rt")

def cal(val1, val2, op):
    if op == "+":
        return val1 + val2
    elif op == "-":
        return val1 - val2
    elif op == "*":
        return val1 * val2
    elif op == "/":
        return int(val1 / val2)

def DFS(L, value):
    global max_value, min_value
    if L == n-1: # n-1이 됐다는건 n-1개의 연산자를 모두 확인했음
        max_value = max(max_value, value)
        min_value = min(min_value, value)
    else: # 그게 아니라면 현재 값과 연산 진행
        for i in range(4):
            if oper[i] > 0:
                oper[i] -= 1
                res_value = cal(value, data[L+1], operator[i])
                DFS(L+1, res_value)
                oper[i] += 1

operator = ["+", "-", "*", "/"]
T = int(input())
for t in range(1,T+1):
    n = int(input())
    oper = list(map(int, input().split())) # 연산자 각 개수 + - * / 개수 순
    data = list(map(int, input().split())) # 계산에 사용되는 숫자 oper 개수 + 1
    # 첫 숫자부터 계산 시작.
    max_value = -int(1e9)
    min_value = int(1e9)
    DFS(0,data[0])
    # print(f"max_value = {max_value}")
    # print(f"min_value = {min_value}")
    print(f"#{t} {max_value-min_value}")

코멘트

있는 그대로의 완탐 진행
-> 대신 결과를 계속 확인하면서 백트랙킹 하면서 확인. 백트랙킹 시 원상복구 진행

종료조건 : L == n-1
-> n-1이 됐다는 건 n-1개의 연산자 모두 확인했음
그게 아니라면 현재 값과 연산 진행

++ 물론 나누기 연산할 때 소숫점 이하는 버린다 -> int로 감쌌어야 했음