123. 14888(연산자 끼워놓기)

import sys
input = sys.stdin.readline
N = int(input())

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

operator = list(map(int, input().split()))
# 덧셈, 뺄셈, 곱셈, 나눗셈
result = []


def DFS(add, sub, mul, div, value, depth):  
    if depth == N:
        result.append(value)
        return

    if(add != 0):
        DFS(add-1, sub, mul, div, value + num[depth], depth+1)
    if(sub != 0):
        DFS(add, sub-1, mul, div, value - num[depth], depth+1)
    if(mul != 0):
        DFS(add, sub, mul-1, div, value * num[depth], depth+1)
    if(div != 0):
        DFS(add, sub, mul, div-1, int(value / num[depth]), depth+1)


DFS(operator[0], operator[1], operator[2], operator[3], num[0], 1)
print(max(result))
print(min(result))

문제요약

숫자와 연산자가 주어졌을때 나올 수 있는 연산을 모두 고르고, 최대값과 최소값을 출력하시오.

설명

깊이우선탐색을 이용하여 숫자와 모든연산자에서 나오는 결과를 result에 저장하고 최대값과 최소값을 출력하였다.

def DFS(add, sub, mul, div, value, depth):  
    if depth == N:
        result.append(value)
        return

    if(add != 0):
        DFS(add-1, sub, mul, div, value + num[depth], depth+1)
    if(sub != 0):
        DFS(add, sub-1, mul, div, value - num[depth], depth+1)
    if(mul != 0):
        DFS(add, sub, mul-1, div, value * num[depth], depth+1)
    if(div != 0):
        DFS(add, sub, mul, div-1, int(value / num[depth]), depth+1)

깊이와 숫자가 동일하면 끝까지 탐색을 마친것이다.

따라서 return을 통해 종료를 시켜준다.

 

add,sub,mul,div 각 연산자가 0이 아니라는것은 연산 횟수가 아직 남았다는 뜻과 같다.

처리 후 -1을 통해 다시 DFS 함수를 호출한다.

 

DFS(operator[0], operator[1], operator[2], operator[3], num[0], 1)
print(max(result))
print(min(result))

각 연산자의 값을 넘겨주고 처음 value는 num[0]이, depth는 1이 된다.

DFS를 통해 모든 결과값을 넣어 주었으므로 min과 max를 통해 출력을 해주면 된다.