[백준] 14888번 - 연산자 끼워넣기 Python 파이썬

📄 문제

❗️풀이

python3를 이용하여 시간초과가 나지 않기 위해서는 DFS 를 이용하면 된다.
1. 가장 첫번째 숫자를 초기 result로 설정한다.
2. +, -, x, // 순으로 계산할 연산자가 남아있는지(0이 아닌지) 확인 후 해당 연산자를 이용한 계산 결과를 result로 업데이트 한다.
3. 다음 연산을 진행할 수 있도록 해당 연산자의 개수를 하나 줄이고 num_list의 idx를 하나 늘려 재귀함수를 호출한다.
4. 연산을 모두 수행할 때마다 (숫자 list에 접근하는 index == N) total_result에 추가시킨다.
5. 모든 경우의 수에 대한 계산을 마치면 최대, 최소를 구해 출력한다.

✏️ 코드

import sys
input = sys.stdin.readline

N = int(input())
num_list = list(map(int, input().split()))
# +, -, x, //의 개수 
plus, minus, mul, div = map(int, input().split())
total_result = []

def operation(idx, result, plus, minus, mul, div):
    # 연산을 다 했다면 결과값 추가
    if idx == N:
        total_result.append(result)
        return
    
    # addition
    if plus:
        operation(idx+1, result + num_list[idx], plus-1, minus, mul, div)
    # subtraction
    if minus:
        operation(idx+1, result - num_list[idx], plus, minus-1, mul, div)
    # multiplication
    if mul:
        operation(idx+1, result * num_list[idx], plus, minus, mul-1, div)
    # division
    if div:
        if result >= 0: tmp = result // num_list[idx]
        # 음수를 나눌 때에는 C++14의 방식을 따른다(문제 참고)

        else:   tmp = -(-(result)//num_list[idx])
        operation(idx+1, tmp, plus, minus, mul, div-1)


operation(1, num_list[0], plus, minus, mul, div)
print(max(total_result))
print(min(total_result))

처음에 순열(permutation)을 이용해 계산할 수 있는 경우의 수를 다 구한 후 이를 하나씩 수행하는 방식을 이용했더니 python3에서 시간초과가 발생했다.(pypy에서는 된다고 하더라,,) DFS, BFS 예제를 푼지 오래됐더니 적용하는걸 까먹는다. 다시 문제를 풀어야겠다 🥲