14888 연산자 끼워넣기

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

#백트래킹

14888번: 연산자 끼워넣기

#14888 연산자 끼워넣기 정리

def toanswer(index,i,p,m,mul,div):

#백트래킹할 함수 toanswer

global max_answer

global min_answer

#계속 갱신할 수 있게 하기 위해서 global 즉 전역함수로 지정한다.

if index==len(l):

max_answer=i if max_answer

min_answer=i if min_answer>i else min_answer

#백트래킹을 끝낼 조건 : l을 전부 돌았을때 갱신한다.

if p>0:

toanswer(index+1,i+l[index],p-1,m,mul,div)

if m>0:

toanswer(index+1,i-l[index],p,m-1,mul,div)

if mul>0:

toanswer(index+1,i*l[index],p,m,mul-1,div)

if div>0:

if l[index]>0 and i<0:

toanswer(index+1,-(-i//l[index]),p,m,mul,div-1)
#4종류의 중복 순열, 이 부분이 이 문제에서 핵심인데, 그냥 단순하게 index를 두개 돌려서 하자고 생각을 하면 중복되는 #것들과 순서를 생각하기 어렵고 l을 움직이기에는 l의 수가 11개가 넘는다. 고로 이미 확정되어 있는 4가지 +-*/을 나열 #해놓고 백트래킹을 실행한다.
else:

toanswer(index+1,i//l[index],p,m,mul,div-1)

 

n=int(input())

#수의 개수 n 입력

l=list(map(int,input().split()))

#수의 개수를 기반으로 한 수 리스트 나열

yonsan=list(map(int,input().split()))

#+ - * / 리스트 입력

i=l[0]

#초기값 l[0]

max_answer=-1000000001

min_answer=1000000001

#max_answer 와 min_answer 초기값 설정(어떤 수가 나와도 초기값이 설정 되도록 최대 최소값으로)

toanswer(1,i,yonsan[0],yonsan[1],yonsan[2],yonsan[3])

#+ - * / 을 분해 해서 함수에 입력

print(max_answer)

print(min_answer)

 

#백트래킹의 기초격인 문제 다른 알고리즘 없이 백트래킹만 알고있다면 풀 수있는 문제이다. 단 중간에서 보았듯이 핵심을 알아야 한다. 백트래킹에서 문제가 복잡해질 경우에는 고정되어있고 예상가능한 요소가 무엇인지 그것을 분해해서 백트래킹의 세부적인 요소로 만들 수 있는지를 분석하는 능력이 필요한 그런 문제였다. 백트래킹의 기초지만 이것을 모르면 풀 수가 없는 문제이다.