백준 14888 연산자 끼워넣기 - python

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

14888번: 연산자 끼워넣기

풀이:

n = int(input())
a = list(map(int, input().split()))
ysj = list(map(int, input().split()))

maximum = -1e9
minimum = 1e9

def dfs(depth, tot, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == n:
        maximum = max(tot, maximum)
        minimum = min(tot, minimum)
        return
    
    if plus:
        dfs(depth + 1, tot + a[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, tot - a[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, tot * a[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(tot / a[depth]), plus , minus, multiply, divide - 1)
        
dfs(1, a[0], ysj[0], ysj[1], ysj[2], ysj[3])
print(maximum)
print(minimum)

결론적으로 풀지는 못했는데 접근한 과정에서 풀이까지 설명하려한다.

 

일단 문제는 제시된 숫자는 배열을 바꿀수 없고 주어진 연산자의 개수만큼 자유롭게 연산해야한다. 

 

처음엔 풀이에서 주어진 a를 for 문으로 잡고 시작을 했는데 생각을 좀 더 해보니....

 

DFS를 써야하는거 a가 아니라 연산과정이였다. 

+ 를 선택 했으면 다음 선택지는 + - * / 고 그 다음은 또 4개가 나누어지는 가지치기 형식의 그림을 떠올렸고 

그대로 코드를 짜면 됐다. 

하지만 위 풀이처럼 저렇게 if 문으로 재귀를 돌리는 생각은 하지 못했다.

 

문제를 다시 보면 최대값과 최소값을 초기화 시켜주고 재귀함수에서 숫자의 개수에 도달하면 최대값과 최솟값을 정해준다.

 

그 밑은 연산자가 있으면 그 연산자를 계산해주고 개수를 하나씩 지우면서 계속 반복하면된다. 

 

( 근데 if 문을 저렇게 쓰면 무조건 plus 부터 시작하지 않나요? .. 1 - 2 + 3 ... 이런것도 계산 하는 걸 보면 if 문이 순서 없이 각자 파트에서 돌린다고 유추 했는데... 맞나요?)