[SW4008][DFS] 숫자 만들기

SW4008 숫자 만들기

SW Expert Academy

 

• 내 풀이
  • 순열로 푸니까 시간초과

from itertools import permutations 

def operate(n1,n2,o):
    if o=='+':
        return n1+n2
    elif o=='-':
        return n1-n2
    elif o=='*':
        return n1*n2
    else:
        return int(n1/n2)
          

T= int(input())

for test_case in range(1,T+1):
    n=int(input())
    operator="+-*/"
    lst=list(map(int,input().split()))

    op=""
    
    for idx,ls in enumerate(lst):
        op+=operator[idx]*ls

    num=list(map(int,input().split()))

    #set으로 중복 제거
    #연산자 개수: n-1
    pmt=set(permutations(op,n-1))

    first=num.pop(0) #하나 줄여서 연산자랑 개수 맞춤
    
    max_val,min_val=-1e9, 1e9
    for pm in pmt:
        result=first #매연산 돌아갈때 첫숫자부터 다시 계산
        for n, p in zip(num, pm):
            result=operate(result, n, p)
          
        max_val=max(max_val,result)
        min_val=min(min_val,result)

    print("#%d %d"%(test_case,max_val-min_val))

• DFS

T= int(input())

for test_case in range(1,T+1):
    
    N = int(input())
    op = list(map(int, input().split()))  # +, -, *, //  
    num = list(map(int, input().split()))
    
    
    max_val = -1e9
    min_val = 1e9
    
    
    def dfs(depth, total, plus, minus, multiply, divide):
        global max_val, min_val
        if depth == N:
            max_val = max(total, max_val)
            min_val = min(total, min_val)
            return
    
        if plus:
            dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
        if minus:
            dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
        if multiply:
            dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
        if divide:
            dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)
    
    
    dfs(1, num[0], op[0], op[1], op[2], op[3])
    print("#%d %d"%(test_case,max_val-min_val))