14888. 연산자 끼워넣기

문제

N개의 수로 이루어진 수열 A1, A2, …, AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

1+2+3-4×5÷6

1÷2+3+4-5×6

1+2÷3×4-5+6

1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

1+2+3-4×5÷6 = 1

1÷2+3+4-5×6 = 12

1+2÷3×4-5+6 = 5

1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

풀이

경우의 수를 모두 조합 후, 나온 결과값을 비교하는 브루트 포스 방식이다. DFS 와 재귀를 활용하여 풀었다. itertools의 permutation으로도 풀 수 있지만 속도도 느리고 코딩테스트에서 제한도 두기 때문에 최대한 배제하고 있다.

import sys

def dfs(val, index, plus, minus, mul, div):
    global n, maxv, minv
    if index == n:
        minv = min(val, minv)
        maxv = max(val, maxv)
        return

    if plus:
        dfs(val+input_list[index], index+1, plus-1, minus, mul, div)
    if minus:
        dfs(val-input_list[index], index+1, plus, minus-1, mul, div)
    if mul:
        dfs(val*input_list[index], index+1, plus, minus, mul-1, div)
    if div:
        dfs(int(val /input_list[index]), index+1, plus, minus, mul, div-1)

if __name__ == "__main__":
    minv = sys.maxsize
    maxv = -sys.maxsize-1
    n = int(input()) # 2
    input_list = list(map(int ,input().split())) # [5, 6]
    a, b, c, d = map(int, input().split()) # 0, 0, 1, 0
    dfs(input_list[0], 1, a, b, c, d)
    print(maxv) # 30
    print(minv) # 30