[백준/BOJ/알고리즘/파이썬(python)]#14888_연산자 끼워넣기

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

14888번: 연산자 끼워넣기

백트래킹으로 분류되어 있는 문제로

연산자 4개의 순열조합을 통해 연산을 진행하는 탐색 문제다.

재귀를 사용하는 방법도 있지만 시간적 비용을 줄이기 위해 반복을 사용하여 풀었다.

파이썬은 permutation이라는 매우 편한 itertools 라이브러리가 있어서 중복제거를 위한 조합 로직을 C나 C++처럼 다 짤 필요가 없다.

재귀를 사용한다면 조합 로직을 쓰지 않아도 되지만, 반복을 사용하기 때문에 연산자 조합 리스트를 만들어야 한다.

 

 

파이썬 코드

#14888
from itertools import permutations
import sys
input = sys.stdin.readline

N = int(input().strip())
num_list = list(map(int, input().strip().split()))
op_list = list(map(int, input().strip().split()))

max_result = -1000000000
min_result = 1000000000

operator = ['+','-','*','/']
op_per = []
for i in range(4):
    for j in range(op_list[i]):
        op_per.append(operator[i])
        
op_per = list(set(permutations(op_per, len(op_per))))



for j in op_per:
    result = num_list[0]
    for i in range(0,N-1):
        #+
        if j[i]=='+':
            result = result + num_list[i+1]
            op_list[0]-=1
        #-
        elif j[i]=='-':
            result = result - num_list[i+1]
            op_list[1]-=1
        #x
        elif j[i]=='*':
            result = result * num_list[i+1]
            op_list[2]-=1
        #/
        elif j[i]=='/':
            if result<0:
                result = -(-result // num_list[i+1])
            else:
                result = result // num_list[i+1]
            op_list[3]-=1
        if i==N-2:
            max_result = max(max_result, result)
            min_result = min(min_result, result) 
   
print(max_result)
print(min_result)