백준 - 15659번: 연산자 끼워넣기 (3)

목차

• 문제명
• 문제풀이
• 코드

 

연산자 끼워넣기 (3)

 

문제 유형 : DFS, 백트래킹

난이도 : 골드 4

 

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

 

 

 

문제 풀이

 

백트래킹 문제이므로 기저조건으로 N - 1개의 연산자를 모두 썼을때 식을 계산하여 최대, 최소 값을 구한다.

 

함수를 재귀적으로 호출하는 조건은, 사용가능한 연산자가 남아있을 경우이다.

 

 

코드

 

N = int(input())
A = list(map(int, input().split()))
plus, minus, multi, div = map(int, input().split())
max_ans = int(-1e11)
min_ans = int(1e11)


def rec(string, p, m1, m2, d, cnt):
    if cnt == N:
        global max_ans, min_ans
        result = eval(string)
        max_ans = max(max_ans, result)
        min_ans = min(min_ans, result)
        return

    if p > 0:
        rec(string + '+' + str(A[cnt]), p - 1, m1, m2, d, cnt + 1)
    if m1 > 0:
        rec(string + '-' + str(A[cnt]), p, m1 - 1, m2, d, cnt + 1)
    if m2 > 0:
        rec(string + '*' + str(A[cnt]), p, m1, m2 - 1, d, cnt + 1)
    if d > 0:
        rec(string + '//' + str(A[cnt]), p, m1, m2, d - 1, cnt + 1)


rec(str(A[0]), plus, minus, multi, div, 1)

print(max_ans)
print(min_ans)

 

 

마무리