[B0J - 14888 연산자 끼워넣기(2)] 브루트포스(순열) python

문제조건

연산자를 N-1개 나열하여 숫자를 계산한다. (순열)

핵심개념

• 재귀함수와 check 배열을 사용하여 순열을 만들거나
• 재귀함수와 cnt 배열을 사용한다. 

(1) 재귀함수와 check배열 사용하는 방법 (시간초과가 나는데 ㅠㅠ)

# 입력받기
n = int(input())
num = list(map(int, input().split()))
cnt = list(map(int, input().split()))

# 연산자 중에서
cal = [0] * cnt[0] + [1] * cnt[1] + [2] * cnt[2] + [3] * cnt[3]
# n-1 개를 뽑은 순열
a = [0] * (n - 1)
# 연산자 중복 체크용
check = [False] * (len(cal))
# 계산값
ans = []

# n-1개 연산자 순열 뽑는 함수
def go(idx, c, m):
    if idx == m:
        calculate(a)
        return

    for i in range(len(c)):
        if check[i]:
            continue
        check[i] = True
        a[idx] = c[i]
        go(idx+1, c, m)
        check[i] = False


# 연산자 순열대로 계산하는 함수
def calculate(a):
    result = num[0]
    global ans
    i = 0
    for j in a:
        i += 1
        if j == 0:
            result += num[i]
        if j == 1:
            result -= num[i]
        if j == 2:
            result *= num[i]
        if j == 3:
            result = int(result / num[i])
    ans.append(result)


go(0, cal, n - 1)
print(max(ans))
print(min(ans))

(2) 재귀함수와 cnt 배열 사용하는 방법

# 입력받기
n = int(input())
num = list(map(int, input().split()))
cnt = list(map(int, input().split()))
max_ans = -1000000000
min_ans = 1000000000

def go(idx, m, ans):
    global max_ans, min_ans

    if idx == m:
        max_ans = max(max_ans, ans)
        min_ans = min(min_ans, ans)
        return

    if cnt[0] > 0:
        cnt[0] -= 1
        go(idx+1, m, ans+num[idx])
        cnt[0] += 1

    if cnt[1] > 0:
        cnt[1] -= 1
        go(idx+1, m, ans-num[idx])
        cnt[1] += 1

    if cnt[2] > 0:
        cnt[2] -= 1
        go(idx+1, m, ans*num[idx])
        cnt[2] += 1

    if cnt[3] > 0:
        cnt[3] -= 1
        go(idx+1, m, int(ans/num[idx]))
        cnt[3] += 1

go(1, n, num[0])
print(max_ans)
print(min_ans)