[백준] 14888 : 연산자 끼워넣기

문제

풀이

python 코드로 제출하면 시간초과되고 pypy로 제출하면 맞추긴 하는 코드
DFS로 풀면 python으로도 제출할 수 있다고 한다!

import sys
import itertools

n = int(sys.stdin.readline())
nlist = list(map(int, sys.stdin.readline().split()))
mlist = list(map(int, sys.stdin.readline().split()))
olist = ["+", "-", "*", "%"] # 따로 리스트 만들어주고 인덱스 번호 같게 해서 매칭시켜주기
plist = []

for i in range(len(mlist)):
    for j in range(mlist[i]):
        plist.append(olist[i])

perm = list(itertools.permutations(plist, len(plist)))

result = []
for i in range(len(perm)):
    r = nlist[0]
    for j in range(len(plist)):
        if perm[i][j] == "+":
            r += nlist[j+1]
        elif perm[i][j] == "-":
            r -= nlist[j+1]
        elif perm[i][j] == "*":
            r = r * nlist[j+1]
        elif perm[i][j] == "%":
            if r < 0:
                a = abs(r)//nlist[j+1]
                r = -a
            else:
                r = r//nlist[j+1]
    result.append(r)

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

다른 사람 풀이

# 백트래킹 (Python3 통과, PyPy3도 통과)
import sys

input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))  # +, -, *, //

maximum = -1e9
minimum = 1e9


def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        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(maximum)
print(minimum)

제일 이해하기 쉬웠던 코드
https://data-flower.tistory.com/72

참고해서 DFS로 풀어본 풀이

# 연산자 끼워넣기 DFS로 풀어보기
import sys

n = int(sys.stdin.readline())
nlist = list(map(int, sys.stdin.readline().split()))
plus, minus, gop, na = map(int, sys.stdin.readline().split())
minCost = 1e9
maxCost = -1e9

def dfs(depth, total, plus, minus, gop, na):
    global minCost, maxCost
    
    if depth == n: # 모든 연산 다 했을 때
        minCost = min(minCost, total)
        maxCost = max(maxCost, total)
        return # return 해줘야 재귀함수가 끝남!
    
    if plus:
        dfs(depth+1, total + nlist[depth], plus - 1, minus, gop, na)
    if minus:
        dfs(depth+1, total - nlist[depth], plus, minus - 1, gop, na)
    if gop:
        dfs(depth+1, total * nlist[depth], plus, minus, gop - 1, na)
    if na:
        dfs(depth+1, int(total / nlist[depth]), plus, minus, gop, na - 1)   

dfs(1, nlist[0], plus, minus, gop, na)

print(maxCost)
print(minCost)