백준 14888 - 연산자 끼워넣기

숫자 배열이 주어지고, 사용할 수 있는 연산자의 갯수도 주어진다. 

예를 들어서 [1,2,3,4,5,6] 이고 [2,1,1,1]이면 '+'를 2개, '-' 1개, '*' 1개, '%' 1개를 이용할 수 있다.

 

조금 더 작은 수를 예제로 들어보자 

 

숫자 : 3 4 5
사용할 수 있는 연산자 : 1 0 1 0

나올 수 있는 조합은 

3+4*5, 3*4+5 이 있다. 

 

여기서 최댓값, 최솟값을 구하는 문제이다. 

 

나올 수 있는 숫자는 11개이며, 연산자는 10개이다. 

즉 10개의 연산자를 순서대로 배치하면 된다. 

 

문제에서는 숫자 6개에 연산자 5개일때, 경우의 수가 60가지라고 표현을 했다. 

왜 그러냐면 같은것을 하나로 보기 때문이다. 

 

만약 최악의 경우 11개의 숫자가 들어온다면 

'+' 3개, '-' 3개, '*' 2개, '%' 2개 ...가 최대이다.

 

10!

-----

3!3!2!2!

 

이를 계산해보면 25200가지가 최악의 수이다.

 

하나씩 대입해보면서 계산해도 될듯하다...

 

 

결국 이전에 만들었던 next_permutation을 가지고 돌리면서 값을 계산하면 된다

https://hongprogrammer.tistory.com/169

next_permutation, prev_permutation

소스 코드 보기 

def next_permutation(lst):
    i = len(lst) - 1

    while(i > 0 and lst[i-1] >= lst[i]):
        i -= 1
    if(i <= 0):
        return False
    j = len(lst) - 1

    while (lst[i-1] >= lst[j]):
        j -= 1
    lst[i-1], lst[j] = lst[j], lst[i-1]
    j = len(lst) - 1
    while(i < j):
        lst[i], lst[j] = lst[j], lst[i]
        i += 1
        j -= 1
    return True


def div(a, b):
    if a >= 0:
        return a//b
    else:
        return -(-a//b)


def calc(arr, operation_list):
    n = len(arr)
    ans = arr[0]

    for i in range(1, n):
        if operation_list[i-1] == 0:
            ans = ans + arr[i]
        elif operation_list[i-1] == 1:
            ans = ans - arr[i]
        elif operation_list[i-1] == 2:
            ans = ans * arr[i]
        else:
            ans = div(ans, arr[i])

    return ans


t_case = int(input())

arr = list(map(int, sys.stdin.readline().rstrip().split(" ")))
cnts = list(map(int, sys.stdin.readline().rstrip().split(" ")))
operator_list = []
results = []

for i, value in enumerate(cnts):
    for j in range(value):
        operator_list.append(i)


operator_list.sort()

while True:
    temp = calc(arr, operator_list)
    results.append(temp)

    if not next_permutation(operator_list):
        break
results.sort()

print(results[-1])
print(results[0])