[DFS] 백준 14888번 : 연산자 끼워넣기 - Python 파이썬

 

생각하기

수와 수 사이에 연산자가 있는 구성이다. 

근데 연산자들이 한번 사용되면 소진되는 구성이다. 

처음에 생각할때는 다익스트라 구현시, visited 배열을 만드는 것과 같이 이미 사용한 연산자를 체크하는 used배열을 선언하여 체크하려고 했다. 하지만 세번째 테스트케이스에서 결과가 나오지 않는 문제가 있어서 다시 생각하게 되었다. 

또한 굉장히 코드가 복잡해지는 문제가 있었다. return 시에 다시 used 배열을 FALSE 처리하고 나와야하는 등 

코드가 더러워지면 이것은 틀린 것이다! 라는 생각에 다시 생각하게되었다.

 

 

입력받은 연산자의 개수 리스트를 그대로 사용할 방법이 없는가

각 연산자의 개수는 정해져 있고 해당 연산자를 사용할 때마다 소진하는 DFS를 생각해보았다. 

즉, 연산자에 해당하는 개수가 0보다 크다면 지속적으로 연산을 수행해나가면 되는 것이다.

 

경우의 수

예를 들어 숫자가 2, 3, 5, 7 즉 4개의 숫자가 있다면 각 숫자 사이에는 4개의 연산자가 들어갈 수 있다

따라서 4^(N-1) = 2^2(N-1)이 경우의 수이다. 

2<=N<=11 이므로 2^20이 최대이다 이는 1048576이다

 

 

구현하기

dfs 함수 파라미터로 연산자의 개수를 넣어두고 recursive할수록 연산자의 개수를 없애가며 해당 연산을 하는 방식

• dfs메서드를 구현할 때, 처음 시작은 0에서 시작을 한다.
• result는 처음 data[0]을 넣어놓고 연산자에 따라 뒤에 따라오는 숫자를 가지고 계산한다.
• result에 연산자 계산을 하는 것은 Recursive를 할 때 수행한다.
• Data 배열의 최고 인덱스를 넘어갔을 때, 해당 Result가 최소인지, 최대인지 판단한다

import sys
input = sys.stdin.readline

N = int(input())

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

# 0 - +, 1 - -, 3 - *, 4 - /
op_cnt = list(map(int, input().split()))
# op_start = []
# for i in range(4):
#     if op_cnt[i] != 0:
#         op_start.append(i)

# print(op_start)

max = -int(1e9)-1
min = int(1e9)


def search(idx, result, add, sub, mul, div):
    global max, min

    if idx == N:
        if max < result :
            max = result
        if min > result :
            min = result
        
        return

    if add > 0:
        search(idx+1, result+data[idx], add-1, sub, mul, div)
    if sub > 0:
        search(idx+1, result-data[idx], add, sub-1, mul, div)
    if mul > 0:
        search(idx+1, result*data[idx], add, sub, mul-1, div)
    if div > 0:
        if result//data[idx]<0:
            search(idx+1, -((-result)//data[idx]), add, sub, mul, div-1)
        else:
            search(idx+1, result//data[idx], add, sub, mul, div-1)


search(1, data[0], op_cnt[0], op_cnt[1], op_cnt[2], op_cnt[3])
print(max)
print(min)