[SWEA] 4008. 숫자 만들기 (Python)

link 🔗 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH

SW Expert Academy

 

1️⃣ DFS로 나올 수 있는 연산자 조합 구해주기

2️⃣ calculate() 함수로 숫자+연산자, 왼쪽 → 오른쪽 순서로 계산

3️⃣ Max, Min과 비교하여 갱신

 

t = int(input())
 
def calculate(operator):
    global Max, Min
    temp = num[0]
    for i in range(1, N):
        if operator[i-1] == '+':
            temp += num[i]
        elif operator[i-1] == '-':
            temp -= num[i]
        elif operator[i-1] == '*':
            temp *= num[i]
        else:
            temp /= num[i]
            temp = int(temp)
    if Max < temp:
        Max = temp
    if Min > temp:
        Min = temp
 
def dfs(level, operator):
    global cal
    if level == limit:
        calculate(operator)
        return
    for i in range(4):
        if cal[i] > 0:
            cal[i] -= 1
            dfs(level+1, operator+ope[i])
            cal[i] += 1
 
for tc in range(1, t+1):
    N = int(input())
    cal = list(map(int, input().split()))
    num = list(map(int, input().split()))
    ope = ['+', '-', '*', '/']
    limit = sum(cal)
    Max = -1e8
    Min = 1e8
    dfs(0, '') # level, 연산자
    print(f'#{tc} {Max-Min}')