[백준 14888번] 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

---

 

문제 유형: 브루트포스, 백트래킹

 

풀이 과정:

DFS를 이용하여 문제를 해결했다.

최대 최소 값은 모든 조건을 만족하면서 수열의 끝에 도달하게 되면 갱신하는 방식으로 나타냈다.

연산자의 개수가 있는 리스트를 활용하여 백트래킹을 시도하였는데,

연산자의 개수가 0보다 작아지면 다른 연산자에 대한 DFS를 시도하고,

모든 탐색이 끝나고 이전의 리스트로 원상복귀를 하기 위해서 연산자의 개수 +1 를 해줘야한다.

---

#백준14888
n = int(input())
a = list(map(int,input().split()))
oper_num = list(map(int,input().split()))
cnt = 0
min_v = 1e9
max_v = -1e9
def oper(x,y,operator):
    if operator == 0:
        return x+y
    elif operator == 1:
        return x-y
    elif operator == 2:
        return x*y
    else:
        if x<0 and y>0:
            return -(abs(x)//y)
        return x//y
    
def dfs(cnt,val):
    global min_v
    global max_v
    if cnt == len(a)-1:
        min_v = min(min_v,val)
        max_v = max(max_v,val)
    for i in range(4):
        oper_num[i]-=1
        if oper_num[i] <0:
            oper_num[i]+=1
            continue
        dfs(cnt+1,oper(val,a[cnt+1],i))
        oper_num[i]+=1

dfs(0,a[0])
print(max_v)
print(min_v)

* 연산자 리스트의 원상 복귀가 가장 중요한 문제인 것 같다..