연산자 끼워넣기 (삼성 기출) / Silver 1 / 14888번

문제 📋

백준 삼성기출 - 연산자 끼워넣기

풀이 📝

import sys

N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
operators = list(map(int, sys.stdin.readline().split()))
case = ['+', '-', '*', '//']
result = []


def dfs(current_value, next_index, operator, operator_list):
    if operator == "+":
        current_value += numbers[next_index]
        operator_list[0] -= 1
    elif operator == "-":
        current_value -= numbers[next_index]
        operator_list[1] -= 1
    elif operator == "*":
        current_value *= numbers[next_index]
        operator_list[2] -= 1
    else:
        if current_value < 0:
            current_value = -(-current_value // numbers[next_index])
        else:
            current_value //= numbers[next_index]
        operator_list[3] -= 1

    if sum(operator_list) == 0:
        result.append(current_value)
        return
    else:
        for j in range(4):
            if operator_list[j] != 0:
                dfs(current_value, next_index + 1, case[j], operator_list[:])


for i in range(4):
    if operators[i] != 0:
        dfs(numbers[0], 1, case[i], operators[:])

print(max(result))
print(min(result))

숫자의 최대 개수가 11개이기 때문에 연산자의 최대 개수는 10개이다.
연산자의 종류는 총 4개 있으므로 만약 + 3개, - 3개, * 2개 % 2개 라면
경우의 수가 10! / 3! 3! 2! 2! 정도이기 때문에
완전 탐색으로 풀어도 시간 초과가 나지 않을 것이라 생각했다.

따라서 DFS를 사용하여 탐색을 진행하였으며 최대 depth까지 갔을 때
즉, operators = [0, 0, 0, 0]이 될 때까지 값을 계산하고 결과를 result 리스트에 넣어주었다.

특이사항으로는 각 Path마다 operator 리스트를 따로 관리해야 되기 때문에 인자로 복사본인 opertators[:]를 넣어주었다.