[백준 14888번] 연산자 끼워넣기 (파이썬/python)

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

처음에 무식하게 풀었다. 모든 연산자를 따로 리스트에 저장하고

그 연산자를 가지고 순열을 만들어서 모든 경우를 탐색했다..

순열을 가지고 탐색하는거까진 좋은데 연산자를 따로 리스트에 저장하는게 조금 무리였다.

pypy3로만 합격이였고 python3에서는 시간초과났다.

 

 

 

풀이를 조금 변경해서 dfs로 풀었다.

코드 보면 직관적으로 이해갈듯!

 

1번풀이. pypy3로만 합격할수있음(비효율)

import sys
from itertools import permutations
 
input = sys.stdin.readline
 
n = int(input())
num_list = list(map(int, input().split()))
operator_list = list(map(int, input().split()))
op_list = []
result_list = []
 
for idx, o in enumerate(operator_list):
    if idx == 0:
        op_list += ["+"] * o
    elif idx == 1:
        op_list += ["-"] * o
    elif idx == 2:
        op_list += ["*"] * o
    else:
        op_list += ["/"] * o
 
 
def operator(op_idx, a, b):
    if op_idx == '+':
        return a + b
    elif op_idx == '-':
        return a - b
    elif op_idx == '*':
        return a * b
    else:
        return int(a / b)
 
 
for op_l in permutations(op_list, len(op_list)):
    result = num_list[0]
    idx = 1
    for o in op_l:
        result = operator(o, result, num_list[idx])
        idx += 1
 
    result_list.append(result)
 
print(max(result_list), min(result_list), sep="\n")
 

 

 

2번째풀이. 보다 효율적인 코드

import sys
 
input = sys.stdin.readline
n = int(input())
numbers = list(map(int, input().split()))
# 각각의 갯수를 저장
add, sub, mul, div = map(int, input().split())
max_num, min_num = -100000000, 1000000000
 
 
def dfs(i, res, add, sub, mul, div):
    global max_num, min_num
    if i == n:
        if res > max_num:
            max_num = res
        if res < min_num:
            min_num = res
        return
 
    else:
        if add:
            dfs(i + 1, res + numbers[i], add - 1, sub, mul, div)
        if sub:
            dfs(i + 1, res - numbers[i], add, sub - 1, mul, div)
        if mul:
            dfs(i + 1, res * numbers[i], add, sub, mul - 1, div)
        if div:
            dfs(i + 1, int(res / numbers[i]), add, sub, mul, div - 1)
 
 
dfs(1, numbers[0], add, sub, mul, div)
print(max_num,min_num,sep='\n')