14888-백준-연산자 끼워넣기

1. 문제 출처

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

2. 풀이

일단 문제 대로 eval을 사용하여 구현해 보았다..

특정 부분에서 잘못 계산되는 것 같다...반례를 찾을 수 없어서 DFS로 다시 구현하였다.(반례 찾으시면 말해주시면 감사하겠습니다.)

from itertools import  permutations
# 입력
N = int(input())

num_list = list(map(int,input().split()))
operator_list  = list(map(int,input().split()))
operator_list = \
["+"]*operator_list[0]+["-"]*operator_list[1] +\
["*"]*operator_list[2]+["/"]*operator_list[3]

def solution ():
    # 최소 최대값
    max_result = -10e9
    min_result = 10e9
    # 모든 중복되지 않는 순열 구하기
    operators_list = set(permutations(operator_list , (N-1)))
    # 하나의 식으로 만들기
    for operators in operators_list:
        expression = []
        for idx in range(N-1):
            expression.append(num_list[idx]) 
            expression.append(operators[idx]) 
        expression.append(num_list[-1])
        # 계산
        temp = get_eval(expression)
        # 최대값
        max_result = max(temp,max_result)
        # 최소값
        min_result = min(temp,min_result)
    # 출력
    print(f'{max_result}\n{min_result}')
    
def get_eval(expression):
    # eval 을 이용하여 식을 앞부터 계산한다.
    result = eval(f"{expression[0]}{expression[1]}{expression[2]}")
    for idx in range(3,len(expression),2):
        result = int(eval(f"{result}{expression[idx]}{expression[idx+1]}"))
    return result

        
solution()

이건 DFS로 구현한 것 이다.

# 입력

N = int(input())

num_list = list(map(int,input().split()))
operator_list  = list(map(int,input().split()))
max_result = -10e9
min_result = 10e9

# DFS와 재귀를 이용한다.
def dfs (count,result):
    # 전역변수로 설정
    global max_result, min_result,operator_list
    # 만약 식을 전부 계산 하였다면
    if count == N:
        max_result = max(max_result,result)
        min_result = min(min_result,result)
        return
    else:
        # 각각 연산자가 다 떨어질 때 까지 재귀를 통해 결과를 구한다.
        if operator_list[0] > 0:
            operator_list[0] -= 1
            dfs(count+1,result+num_list[count])
            operator_list[0] += 1
            
        if operator_list[1] > 0:
            operator_list[1] -= 1
            dfs(count+1,result-num_list[count])
            operator_list[1] += 1
            
        if operator_list[2] > 0:
            operator_list[2] -= 1
            dfs(count+1,result*num_list[count])
            operator_list[2] += 1
            
        if operator_list[3] > 0:
            operator_list[3] -= 1
            dfs(count+1,int(result/num_list[count]))
            operator_list[3] += 1
        
            
        
    
    


dfs(1,num_list[0])
print(max_result)
print(min_result)