[v.백트래킹-연산자 끼워넣기-14888]BAEKJOON_Python

220127 작성

<본 블로그는 BAEKJOON 을 참고해서 저만의 풀이를 작성하였습니다>

 

 

 

14888

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어짐
둘째 줄에는 A1, A2, ..., AN이 주어짐 (1 ≤ Ai ≤ 100)
셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)의 개수

 

 

내 풀이

from itertools import permutations
import sys

n = int(sys.stdin.readline())

num = list(map(int, input().split()))
op_num = list(map(int, input().split()))
op = ["+", "-", "*", "/"]
oper = []

for i in range(len(op_num)) :
    for j in range(op_num[i]) :
        oper.append(op[i])

max = -1e9
min = 1e9

def solve() :
    global max, min
    for case in permutations(oper, n-1) :
        total = num[0]

        for i in range(1, n) :
            if case[i - 1] == "+" :
                total += num[i]
            elif case[i - 1] == "-" :
                total -= num[i]
            elif case[i - 1] == "*" :
                total *= num[i]
            elif case[i - 1] == "/" :
                total = int(total/num[i])
        
        if total > max :
            max = total
        if total < min :
            min = total

solve()

print(max)
print(min)

 

 

 

 

 

 

 

2
5 6
0 0 1 0
// 결과
30
30

 

 

 

 

 

 

 

 

 

 

 

참고 했숩니댜우 ㅡㅜㅡㅜ

https://velog.io/@kimdukbae/BOJ-14888-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0-Python

[BOJ 14888] 연산자 끼워넣기 (Python)