[백준] 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

dfs를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

N개의 수와, N-1개의 연산자가 주어지면, 연산자를 적절하게 배열하여, 앞에서 부터 계산하였을 때, 최댓값과 최솟값을 return해야 하는 문제입니다. (이 때, 연산자는 +,-,*,/ 가 있습니다. 또 N개의 수의 위치는 고정되어 있다고 가정하고, 연산자의 위치만 바꾸어야 합니다.)

 

<Solution>

최댓값과 최솟값을 모두 구해야 하므로, 특정 수가 가능한지 불가능 한지는 끝까지 계산을 해보지 않고는 모릅니다. 따라서 가지치기 등의 방법을 중간에 할 수 없습니다.

 

dfs를 쭉 해서 결과를 return 시켜야 합니다.

 

실제 구현은 아래와 같습니다. 

import sys

N = int(sys.stdin.readline().rstrip())
num_list = list(map(int,sys.stdin.readline().rstrip().split()))
num_operator = list(map(int,sys.stdin.readline().rstrip().split())) # + - x /

min_ans = int(2e9)
max_ans = -int(2e9)

def dfs(val, times):
    global min_ans, max_ans

    # print(f'val, times : {val, times}')
    if times == N-1:
        min_ans = min(min_ans, val)
        max_ans = max(max_ans, val)
        return

    if num_operator[0] > 0:
        num_operator[0] -= 1
        dfs(val+num_list[times+1], times+1)
        num_operator[0] += 1
    
    if num_operator[1] > 0:
        num_operator[1] -= 1
        dfs(val-num_list[times+1], times+1)
        num_operator[1] += 1

    if num_operator[2] > 0:
        num_operator[2] -= 1
        dfs(val*num_list[times+1], times+1)
        num_operator[2] += 1

    if num_operator[3] > 0:
        num_operator[3] -= 1
        dfs(abs(val) // num_list[times+1] if val >=0 else -(abs(val) // num_list[times+1]), times+1)
        num_operator[3] += 1

dfs(num_list[0], 0)

print(max_ans)
print(min_ans)