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개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

 

문제 풀이

해당문제는 전형적인 DFS로 푸는 문제이다. 그러나 한 가지 염두해야할 점이 ++++가 4개인 경우 ++++의 순서의 상관없이 모두 같은 값이 나오지만 만약 ++++의 모든 가짓수를 순서도 포함해서 신경쓰고 진행했다면 총 24가지의 경우가 나올 수 있다. 그렇기 때문에 이를 염두해두고 문제를 풀면 된다. 

import sys

# input = sys.stdin.readline
N = int(input())
K = list(map(int, input().split()))
op = list(map(int, input().split()))  # +, -, *, //

acc = [-float('inf'), float('inf')]

ans = []

def dfs( count, sum_dfs, plus, minus, multi, divide) :
    if count == len(K) :
        ans.append(sum_dfs)
        acc[0] = max(sum_dfs, acc[0])
        acc[1] = min(sum_dfs, acc[1])
        return
    if plus :
        dfs(count+1, sum_dfs + K[count], plus - 1, minus, multi, divide )
    if minus :
        dfs(count+1, sum_dfs - K[count], plus, minus-1, multi, divide )
    if multi :
        dfs(count+1, sum_dfs * K[count], plus, minus, multi-1, divide )
    if divide :
        dfs(count+1, int(sum_dfs / K[count]), plus, minus, multi, divide-1)

dfs(1, K[0], op[0], op[1], op[2], op[3])

print(acc[0])
print(acc[1])
print(len(ans))

'''
54
-24
60
'''

일단 대중적으로 알려진 방법은 위와 같은 방법이다. 각각의 연산자를 매개변수로 포함시켜 조합과 순열을 동시에 적용 시킬 수 있는 DFS방법으로 풀었다. 

 

다음은 permutations를 활용한 방법이다. 

from itertools import *
import sys

# input = sys.stdin.readline
N = int(input())
K = list( map(int, input().split()) )
J = list( map(int, input().split()) )

op = []
for i, p in enumerate(['+', '-', '*', '/']) :
    op.extend([ p for j in range( J[i] ) ])

acc = [ -float('inf'), float('inf') ]

def solve() :
    for p in set(permutations( op, len(op))): 
        sum_dfs = K[0]
        for i, _p in enumerate(p) :
            # exec( 'sum_dfs' + op[_p] + '=K[i+1]' )
            # sum_dfs = int(eval( 'sum_dfs' + op[_p] +'K[i+1]' ))
            if _p == '+': sum_dfs += K[i+1]
            if _p == '-': sum_dfs -= K[i+1]
            if _p == '*': sum_dfs *= K[i+1]
            if _p == '/': sum_dfs /= K[i+1]
            sum_dfs = int(sum_dfs)
        if sum_dfs > acc[0] : acc[0] = sum_dfs
        if sum_dfs < acc[1] : acc[1] = sum_dfs

solve()

print(acc[0])
print(acc[1])

지금 식을 보면 set(permutations( op, len(op))) 즉 set을 붙여 두었다. 이렇게 진행한 이유는 set은 unique하게 항상 정리가 됨으로 ++++이 연속적으로 나오더라도 하나로 줄여서 저장되기에 시간복잡도를 급격하게 줄일 수 있다.