[백준] 연산자 끼워넣기 14888번 (python)

Algorithm

[백준] 연산자 끼워넣기 14888번 (python)

salmon16 2021. 6. 10. 11:54

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수,

www.acmicpc.net

풀이 방법

DFS로 완전 탐색으로 풀어야 한다.

연산자를 배열로 따로 넣어 두고 각 연산자가 남아 있으면 사용하고 연산자 배열에서 -1을 해주고

dfs를 호출하고 다시 연산자 배열에서 +1을 해주는 백트레킹 방식으로 풀이 하였다.

max_num = -987654321
min_num = 987654321
def dfs(index, sum):
    global min_num, max_num,path
    if index == N:
        min_num = min(min_num, sum)
        max_num = max(max_num, sum)
    for i in range(4):
        if (arithmetic[i] > 0):
            if (i == 0):
                arithmetic[i] -= 1
                dfs(index+1, sum+num[index])
                arithmetic[i] += 1
            elif(i == 1):
                arithmetic[i] -= 1
                dfs(index + 1, sum-num[index])
                arithmetic[i] += 1
            elif (i == 2):
                arithmetic[i] -= 1
                dfs(index + 1, sum * num[index])
                arithmetic[i] += 1
            elif (i == 3):
                arithmetic[i] -= 1
                dfs(index + 1,  int(sum / num[index]))
                arithmetic[i] += 1

N = int(input())
num = []
arithmetic = []
num = list(map(int, input().split()))
arithmetic = list(map(int, input().split()))

dfs(1, num[0])
print(max_num)
print(min_num)