[BOJ] 14888 연산자 끼워넣기_DFS

연산자 끼워넣기

link

내 풀이

• 방식 : BFS
• BFS 방식으로 풀어 전체 경우의 연산값을 가지고 있어야함

📰code

from collections import deque

def cal(op,a,b):
    if op == 0: return a+b
    elif op == 1: return a-b
    elif op == 2: return a*b
    else : 
        if b != 0: 
            if a<0: return -(-a//b)
            else : return a//b
        else : return
from collections import deque

c = int(input())
num = list(map(int,input().split()))
p,m,mul,div = list(map(int,input().split()))

s = num[0]
n = 1
q = deque()
q.append((n,s,p,m,mul,div))
max_sum = -1e9
min_sum = 1e9

while q:
    n,s,p,m,mul,div = q.popleft()
    if n == c:
        if max_sum<s: max_sum = s
        if min_sum>s: min_sum = s
    else : 
        oper = [p,m,mul,div]
        for i in range(4):
            if oper[i] != 0:
                if i ==4 and num[n] == 0: continue
                oper[i]-=1
                q.append((n+1,cal(i,s,num[n]),oper[0],oper[1],oper[2],oper[3]))
                oper[i]+=1
print(max_sum)
print(min_sum)

다른 풀이

• 방식 : DFS
• 최소값만 저장하면 되기 때문에 공간 효율성이 높아짐

📰code

N = int(input())
A_list = [int(x) for x in list(input().split())]
op = [int(x) for x in list(input().split())]

result = []
def operation(ex_val, idx, hap, sub, mul, div):
    # 계산이 끝났다면, max와 min 값과 비교
    if idx == N:
        result.append(ex_val)
        return

    if hap > 0:
        val = ex_val + A_list[idx]
        operation(val, idx+1, hap-1, sub, mul, div)
    if sub > 0:
        val = ex_val - A_list[idx]
        operation(val, idx+1, hap, sub-1, mul, div)
    if mul > 0:
        val = ex_val * A_list[idx]
        operation(val, idx+1, hap, sub, mul-1, div)
    if div > 0:
        val = int(ex_val/A_list[idx])
        operation(val, idx+1, hap, sub, mul, div-1)

operation(A_list[0], 1, op[0], op[1], op[2], op[3])

print(max(result))
print(min(result))

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡