(python) 백준 14888 연산자 끼워 넣기

백트래킹을 이용하여 답을 구하는 문제

 

나는 permutation을 이용하여 모든 경우의 수를 뽑았다.

import itertools
import sys
from functools import reduce
input = sys.stdin.readline
N = int(input())
numbers = list(map(int, input().rstrip().split()))
operators = list(map(int, input().rstrip().split()))

operator_permutation = []
for ind, i in enumerate(operators):
    operator_permutation.extend([ind for _ in range(i)])

operators_excute = {0: lambda x, y : x + y, 1: lambda x, y : x - y, 2 : lambda x, y : x * y, 3 : lambda x, y : int(x / y)}

result = []
oper = [list(x) for x in set(itertools.permutations(operator_permutation))]
for i in oper:
    result.append(reduce(lambda x,y : operators_excute[i.pop()](x,y), numbers))

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

permutaion으로 뽑은 인덱스들을 dict type으로 정의한 lambda 함수들을 매치 시켜 reduce 연산을 했다.

 

dict type의 [ ] 안에 list.pop() 형식으로 가져오면 뒤에서 부터 차례대로 인덱스를 가져온다.

 

[1, 2, 3, 4]면 4 -> 3 -> 2-> 1 이 들어간다. 총 4번 연산