[Python] 백준 14888 연산자 끼워넣기

1. 문제 링크

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

14888번: 연산자 끼워넣기

 

2. 문제 요약

• N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것 구하기

 

3. 아이디어 정리

• 백트래킹으로 진행

1. Base condition(종료 조건): 모든 연산자를 넣은 경우
2. 재귀: 사칙연산을 4개를 돌려 계산을 하고 백트래킹 진행

 

4. 문제 풀이

4-1. 내 풀이

"""
 1. 결과의 최댓값
 2. 최솟값
"""
def dfs(cnt, res):
    global min_
    global max_
    if cnt == n - 1:     # 1. Base condition(종료 조건), 모든 연산자를 넣은 경우
        min_ = min(min_, res)
        max_ = max(max_, res)
        return

    for i in range(4):  # 2. 백트래킹 - 사칙 연산 계산하기 
        temp = res
        if num[i] == 0:  # 해당 사칙 연산이 없는 경우 넘어가기 
            continue
        if i == 0:       # 더하기  
            res += a[cnt + 1]
        elif i == 1:     # 빼기 
            res -= a[cnt + 1]
        elif i == 2:     # 곱하기 
            res *= a[cnt + 1]
        else:            # 나누기 
            if res < 0:
                res = -(abs(res) // a[cnt + 1])
            else:
                res //= a[cnt + 1]
        num[i] -= 1
        dfs(cnt + 1, res)
        num[i] += 1
        res = temp

n = int(input())
a = list(map(int, input().split()))
num = list(map(int, input().split()))   # 연산자 수, 덧셈, 뺄셈, 곱셈, 나눗셈 수
min_ = int(1e9)
max_ = -int(1e9)

dfs(0, a[0])
print(max_)
print(min_)

 

 

5. 결론

• 백트래킹 문제