접근 방법

N^2 (11 * 11) 로 브루트포스로 충분히 풀수있는 문제같다. 하지만 브루트포스로는 구현방법이 떠오르지 않고, 완전탐색 중에서 중복순열 혹은 DFS(백트래킹)으로 풀수있다.

중복순열

import sys
from itertools import permutations
N = int(sys.stdin.readline().strip())
nums = list(map(int,sys.stdin.readline().strip().split()))
play = list(map(int,sys.stdin.readline().strip().split()))
dic = {1:"+",2:"-",3:"*",4:"/"}
ans = []
# + - x // 순
ll = []
for idx,p in enumerate(play):
    for i in range(p):
        ll.append(dic[idx+1])

for item in list(permutations(ll,sum(play))):
    item = list(item)
    result = str(nums[0])
    idx = 1
    while(idx < len(nums)):
        result += str(item[idx-1])
        result += str(nums[idx])
        idx +=1
        print(result)

    ans.append(result)

처음에는 이런식으로 string 을 계속해서 추가해서 모든 경우의 식을 만든뒤 계산을 하려고 했다. 하지만, 너무 복잡해진다..

목적은 식의 값을 찾는 것 이므로, 계속해서 계산을 해가는 방식이 훨씬 좋아 보인다.

import sys
from itertools import permutations
N = int(sys.stdin.readline().strip())
nums = list(map(int,sys.stdin.readline().strip().split()))
play = list(map(int,sys.stdin.readline().strip().split()))
dic = {1:"+",2:"-",3:"*",4:"/"}
ans = []
# + - x // 순
ll = []
for idx,p in enumerate(play):
    for i in range(p):
        ll.append(dic[idx+1])

for item in list(permutations(ll,sum(play))):
    item = list(item)
    total = nums[0]
    idx = 1
    while(idx < len(nums)):
        if item[idx-1] == "+":
            total += nums[idx]
        elif item[idx-1] == "-":
            total -= nums[idx]
        elif item[idx-1] == "*":
            total *= nums[idx]
        elif item[idx-1]=="/":
            if total < 0:
                total = -(abs(total) // nums[idx])
            else:
                total = total // nums[idx]
        idx +=1
    ans.append(total)
ans.sort()
print(ans[-1])
print(ans[0])

DFS(백트래킹)

import sys
N = int(sys.stdin.readline().strip())
nums = list(map(int,sys.stdin.readline().strip().split()))
play = list(map(int,sys.stdin.readline().strip().split()))
ans = []
# + - x // 순
def dfs(result,idx):
 
    if idx==N:
        ans.append(result)
        return
    for i in range(4):
        if play[i] >= 1:
            temp_result = result
            if i == 0:
                temp_result += nums[idx]
       
            elif i == 1:
                temp_result -= nums[idx]
        
            elif i == 2:
                temp_result *= nums[idx]
             
            elif i == 3:
                if temp_result < 0:
                    temp_result = -(-temp_result // nums[idx])  # 음수 나눗셈 처리
                else:
                    temp_result =temp_result // nums[idx]
              
            play[i] -=1
            dfs(temp_result, idx+1)
            play[i] +=1

dfs(nums[0],1)
ans.sort()
print(ans[-1])
print(ans[0])

DFS

물론, 이렇게 백트래킹 말고 DFS같은 구조로 풀이도 가능하다.

import sys
N = int(sys.stdin.readline().strip())
nums = list(map(int,sys.stdin.readline().strip().split()))
play = list(map(int,sys.stdin.readline().strip().split()))
ans = []
# + - x // 순
def dfs(result,idx):
    for i in range(4):
        if sum(play) == 0:
                ans.append(result)
                
        if play[i] >= 1:
            temp_result =result
            if i == 0:
                temp_result += nums[idx]
       
            elif i == 1:
                temp_result -= nums[idx]
        
            elif i == 2:
                temp_result *= nums[idx]
             
            elif i == 3:
                if temp_result < 0:
                    temp_result = -(-temp_result // nums[idx])  # 음수 나눗셈 처리
                else:
                    temp_result =temp_result // nums[idx]
              
            play[i] -=1
            dfs(temp_result, idx+1)
            play[i] +=1

dfs(nums[0],1)
ans.sort()
print(ans[-1])
print(ans[0])