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

from itertools import combinations

def dfs(cu_val,cnt,pick_list):
    global result
    if cnt == 0:
        result = max(result,cu_val*sum(pick_list))
        return cu_val * sum(pick_list)
    else:

        idx_list = range(len(pick_list))
        for pick_cnt in range(1,len(pick_list)-cnt+1):
            for comb in combinations(idx_list,pick_cnt):
                copy_pick_list = pick_list[:]
                comb = list(reversed(comb))
                temp_sum = 0
                for idx in comb:
                    temp_sum += copy_pick_list.pop(idx)                
                dfs(cu_val*temp_sum,cnt-1,copy_pick_list)







N = int(input())

arr = list(map(int,input().split()))

p_cnt,a_cnt = map(int,input().split())


result = 0
dfs(1,a_cnt,arr)
print(result)

 

생각 난대로 풀었더니, 운좋게 풀린 문제였다.

 

이 문제에서 주의해야할 점은 숫자는 순서에 상관없이 배치를 해도 되고, 더하기와 곱셈의 우선순위가 같다.

 

이 2가지를 주의해야한다.

 

이 문제를 풀때 최대값을 구할때 중요하다고 생각한 것이 곱셈이라고 생각했다.

 

 

곱셈을 기준으로 구역을 나누고, 그 사이에 숫자를 집어넣으면 된다고 생각했다.

 

즉 곱셈의 기호가 3개가 주어진다면

 

 

이렇게 4구역으로 나눌수 있다고 생각했다.

 

즉 주어진 숫자들을 4팀으로 나누면 된다.

 

그리고 각 팀은 최소1명이상 이어야만 한다라는 조건을 만족해야한다.

 

그런 방식으로 숫자를 나눠주고, 나뉜 숫자들을 합을 계속 곱해주면서 idx가 마지막까지 올때까지 해주었다.

 

위의 dfs라는 함수가 그것을 의미한다.

 

현재 위치에서 최대로 뽑을 수 있는 숫자는 남은숫자 - 곱셈 기호가 남은개수 만큼 뽑을 수 있다.

 

그렇게 1개부터 (남은숫자 - 곱셈기호가 남은 개수)까지 반복문을 돌리면서

 

숫자들을 뽑아서 재귀를 해주었다.

 

 

# edenooo님 코드 복기
from itertools import permutations
def dfs(idx,cnt,position,num_list):
    global result
    if (cnt+N-1-idx)<Q:
        return
    if idx == N-1:
        position.append(idx)
        mul_val = 1
        sum_val = 0
        cu_idx = 0
        for mul_idx in position:
            while (cu_idx<=mul_idx):
                sum_val += num_list[cu_idx]
                cu_idx += 1
            mul_val *= sum_val
            sum_val = 0
        result = max(result,mul_val)
        position.pop()
        return
    dfs(idx+1,cnt,position,num_list)
    position.append(idx)
    if cnt+1<=Q:
        dfs(idx+1,cnt+1,position,num_list)
    position.pop()
N = int(input())
arr = list(map(int,input().split()))
result = 0
arr.sort()

P,Q = map(int,input().split())
for perm in permutations(arr):
    dfs(0,0,[],perm)
print(result)

이 풀이는 edenooo님의 풀이이다. 기본적인 아이디어는 비슷하다고 볼 수 있다.

 

여기서는 모든 숫자들이 나올 수 있는 배치들을 만들어두고, 곱셈의 위치를 변경시켜서 해주는 방식으로 해주었다.