[BOJ 15658] 연산자 끼워넣기(2) - python

문제조건

• N개의 수가 주어진다. 연산자는 N-1개보다 더 많이 주어질 수 있다.
• N개의 수의 순서는 변하지 않는다. 연산자의 순서만 바뀐다.

핵심개념

• 연산자 개수 중에서 N-1개를 뽑아 순열을 구해야 한다.
• 이를 위해 DFS, 백트래킹을 활용하여 모든 경우의 수를 탐색한다.

python 코드

N = int(input())
a = list(map(int,input().split()))
cnt = list(map(int,input().split()))
max_ans = -1000000000
min_ans = 1000000000

def dfs(idx, ans):
    global max_ans,min_ans
    
    if idx == N:
        max_ans = max(max_ans, ans)
        min_ans = min(min_ans, ans)
        return
    
    if cnt[0] > 0:
        cnt[0] -= 1
        dfs(idx+1, ans+a[idx])
        cnt[0] += 1
    if cnt[1] > 0:
        cnt[1] -= 1
        dfs(idx+1, ans-a[idx])
        cnt[1] += 1
    if cnt[2] > 0:
        cnt[2] -= 1
        dfs(idx+1, ans*a[idx])
        cnt[2] += 1
    if cnt[3] > 0:
        cnt[3] -= 1
        dfs(idx+1, int(ans/a[idx]))
        cnt[3] += 1
        
dfs(1,a[0])
print(max_ans)
print(min_ans)