[Python] BOJ 백준 21943 연산 최대로

문제

---

 N개의 양의 정수 X{i}와 곱하기 연산자, 더하기 연산자가 총 N−1개가 존재하고 괄호는 무수히 많이 사용해도 된다. 이 연산에는 곱하기 연산자와 더하기 연산자의 우선순위가 동일하다.

정수와 연산자는 아래와 같이 배치해야한다. 정수의 순서는 바꿔도 상관없다.

예를 들어 정수 1, 2, 3이 있고 더하기 연산자와 곱하기 연산자가 각각 하나 있다고 가정하면 아래와 같이 만들 수 있다. 

예를 들어, 수 1,2,4,5,7,8와 더하기 연산자가 4개 곱하기 연산자가 1개 있다고 하자. 괄호를 이용하여 최대값을 구하는 방법 중 일부이다.

•  (((1+2)+4)+7)×(5+8)
•  ((1+2)+(4+7))×(5+8)
•  (1+(2+4)+7)×(5+8)
•  (1+2+4+7)×(5+8)

연산을 잘 이용하여 값을 최대로 만들어 보자.

---

풀이

---

이 문제는 꽤 어려웠는데 의외로 한 번에 풀었다. 하지만 고민하는 시간이 매우 길었던 것 같다.

덧셈을 이용해 작은 수들을 큰 수로 만들고, [큰 수 * 큰 수]의 꼴로 만들어야 한다는 것이 핵심 아이디어였는데,

숫자의 순서가 바뀌어도 된다는 부분에서 고민을 많이 했다.

결국 이렇게도 해보고 저렇게도 해보다가 직접 구현했던 조합 함수를 가져와서 이용했다.

특이 사항은 조합 함수에서 next + [arr[i]]로 구현을 한 것인데,

이렇게 한 이유는 dfs 함수 내에서 뽑아낸 조합의 함을 pop으로 꺼내오면서 더해줄 때

뒤에 있는 index부터 꺼내오게 해야 정확하게 원하는 값들을 가져올 수 있다.

import sys

si = sys.stdin.readline


def MIIS(): return map(int, si().split())


n = int(si())
lst = sorted(MIIS())
p, q = MIIS()
answer = 0
'''
곱하기 개수 + 1개 덩어리로 나누어서 각 수의 곱이 최대로 하는 값 찾기
곱하기 개수 + 1개의 덩어리로 나누는 경우의 수를 전부 찾는다.
--> 조합으로 경우의 수 찾아내고 dfs로 max값 갱신시켜나간다. 
'''
# arr에서 r개를 뽑는 조합


def combinations(arr, r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for next in combinations(arr[i+1:], r-1):
                yield next + [arr[i]]

# dfs로 구현


def dfs(arr, count, now):
    # 곱하기가 0이 들어오면 남은 숫자 전부 더하면 된다.
    if count == 0:
        global answer
        answer = max(answer, now * sum(arr))
        return now * sum(arr)
    # 들어온 arr의 인덱스를 가지는 리스트
    idx = range(len(arr))
    for i in range(1, len(arr) - count + 1):
        # j는 [0,1,2,3,4,5]에서 i개를 뽑는 경우의 수
        for j in combinations(idx, i):
            temp = arr[:]
            # print(f"temp = {temp}")
            # 현재 조합의 합을 들어온 이전 결과에 곱해준다.
            multiple_to = 0
            # 인덱스를 기준으로 뽑아내서 담는다.
            for k in j:
                multiple_to += temp.pop(k)
            # print(f"temp_sum = {multiple_to}")
            # 복사한 리스트, 덩어리 하나 선택, 현재 곱셈한 결과 보냄
            dfs(temp, count - 1, now * multiple_to)
    return answer


answer = dfs(lst, q, 1)
print(answer)