백준 14888 연산자끼워넣기 파이썬

문제 링크 : https://www.acmicpc.net/problem/14888

문제

모든 경우의 수를 구하지않고 하는 방법이 있을까?

이 문제에서는 ‘숫자는 고정' 된 상태에서 ‘연산자 순서를 변경' 해서 최대,최소값을 확인하는것이다 과연 이 문제에서 모든 경우의 수를 구하지않고 하는 방법이 있을까?

쉽지않을것같아서 완탐, BFS, DFS계열로 눈을 돌렸다

 

굳이 BFS, DFS로 돌려야하나 ?

가만 생각해보니 무조건 모든 연산자를 다 돌려야하는데, 굳이 BFS,DFS로 돌려야 싶었다.

BFS나 DFS는 ‘특정 조건이 충족되면 진행' 하는거에 특화되어있는거지, 모든 연산을 확인해야하는 경우에 굳이 써야하는 이유를 모르겠어서 안썻다

 

완탐

완전탐색. 모든 경우의 수에 하나씩 대입해보면서 결과를 확인한다

 

연산자 순서 결정하기

#arrs 는 + - * / 횟수가 적혀있는 배열
something = ['+','-','*','/']

strs = ""
for i,j in zip(arrs, something) :
    strs += (j*i)

from itertools import permutations
temps = list(permutations(strs))

모든 연산자의 총 횟수를 하나의 strs로 모은 뒤에 permutations를 사용해서 순열을 만든다

중복되는 순열이 있을수도 있다. 그러나 시간초과나 메모리초과가 나지않아서 신경쓰지않았다

소스코드 (전체)

# N = 6
# datas = [1, 2, 3, 4, 5, 6]
# arrs = [2, 1, 1, 1]

import sys 
input = sys.stdin.readline 

N = int(input().strip())
datas = list(map(int , input().split()))
arrs = list(map(int , input().split()))

something = ['+','-','*','/']
strs = ""
for i,j in zip(arrs, something) :
    strs += (j*i)

from itertools import permutations
temps = list(permutations(strs))
max_result = -999999999
min_result = 999999999

for temp in temps : 
    result = datas[0]
    for data in zip ( datas[1:],temp) : 
        if data[1] == '+' :
            result += data[0]
        elif data[1] == '-' :
            result -= data[0]
        elif data[1] == '*' :
            result *= data[0]
        else : 
            if result >= 0 :
                result //= data[0]
            else : 
                result = (result*(-1) // data[0]) *(-1)
    max_result = max(max_result,result)
    min_result = min(min_result,result)

print(max_result)
print(min_result)