[BOJ 14888] 연산자 끼워넣기 (Python)

문제

문제 바로가기

풀이

위 문제를 보고 2가지 풀이 방법이 떠올랐다. 첫번쨰는 연산자 파이썬에서 지원하는 permutations 모듈을 이용하여 푸는 방법과, 하나는 DFS를 이용하여 (백트래킹) 최대, 최솟값을 구하는 방법이다. permutations 모듈을 사용하여 풀면 구현 자체는 쉬울진 몰라도, 대부분 코테에서
필자는 DFS로 풀이하였다.

주의할점

연산자 우선 순위를 무시하고 무조건 앞에서부터 연산을 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취하며, 음수를 양수로 나눌 때는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다는 점이다.

ex) 1+2÷3×4-5+6는 2가 아니라 5이다

코드

DFS

import sys

input = sys.stdin.readline

n=int(input())
a=list(map(int, input().split()))
op=list(map(int, input().split()))

max_res = -1e9+1
min_res = 1e9+1

def DFS(depth, total, plus, minus, multiply, divide):
    global max_res, min_res
    if depth==n:
        max_res=max(max_res, total)
        min_res=min(min_res, total)
        return 
    
    if plus:
        DFS(depth+1, total+a[depth], plus-1, minus, multiply, divide)
    if minus:
        DFS(depth+1, total-a[depth], plus, minus-1, multiply, divide)
    if multiply:
        DFS(depth+1, total * a[depth], plus, minus, multiply-1, divide)
    if divide:
        DFS(depth+1, int(total/a[depth]), plus, minus, multiply, divide-1)
        
DFS(1,a[0], op[0], op[1], op[2], op[3])
print(max_res)
print(min_res)

참고로 1e9는 1*10의 9승 = 1000000000