[Python/파이썬] 백준 21943번 연산 최대로

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

 

코드

from itertools import combinations

n = int(input())
x = list(map(int, input().split()))
plus, mul = map(int, input().split())

ans = 0


def dfs(picked_cnt, remain_x, total):
    global ans
    if picked_cnt == 1:  # 마지막 덩어리
        ans = max(ans, total*sum(remain_x))
        return
    # 하나의 덩어리 고르기
    for i in range(1, len(remain_x)-picked_cnt+2):
        for comb in combinations(range(len(remain_x)), i):
            new_remain_x = []
            tmp = 0
            for i in range(len(remain_x)):
                if i in comb:
                    tmp += remain_x[i]
                else:
                    new_remain_x.append(remain_x[i])
            dfs(picked_cnt-1, new_remain_x, total*tmp)


dfs(mul+1, x, 1)
print(ans)

 

연산의 결과가 가장 큰 값을 구하려면 곱해지는 피연산자들을 최대한 크게 해야 한다. 그러기 위해서 괄호를 이용하여 덧셈을 먼저 해서 곱할 값들을 최대한 크게 만들면 되는데 이때 괄호 안의 모든 수를 한 덩어리라고 하면 덩어리의 개수는 주어진 곱셈의 수보다 하나 많게 만들면 된다.

위 코드에서는 덩어리를 만드는 모든 경우의 수를 구하기 위하여 DFS를 사용했다. dfs()가 한 번 호출될 때마다 덩어리 하나를 만든다고 생각하면 된다. 아직 선택되지 않은 수들인 remain_x에서 이번 덩어리에 포함될 숫자들을 고르는데, 고르는 숫자의 개수는 1개에서 len(remain_x)-picked_cnt+2개까지만 선택해서 아직 남은 다른 덩어리에도 숫자가 1개 이상 포함될 수 있도록 해준다.