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

문제 설명

 

입력과 출력

 

입출력 예제

 

14888번: 연산자 끼워넣기

---

풀이 코드

이 문제는 푸는 방법이 2가지가 있다.

바로 파이썬의 라이브러리인 permutations(순열)과 DFS로 푸는방법이 있다.

여기서 순열로 풀게 되면 pypy3는 제출 통과하지만 python3으로 제출 시 시간초과가 발생하게 되고 시간복잡도가 높다.

그러므로 나는 DFS로 푸는 방식을 선택하여 이 문제를 풀었다.

 

주어진 숫자들을 처음부터 시작하여, 주어진 부호들을 적용해 가장 크거나 작은 값이 되는 수를 가장 큰 수, 가장 작은 수를 갖는 변수의 값을 갱신하자.

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
signs = list(map(int, input().split()))

maxNum = -1e9
minNum = 1e9

def dfs(depth, total, plus, minus, multiply, divide):
    global maxNum, minNum
    if depth == n:
        maxNum = max(total, maxNum)
        minNum = min(total, minNum)
        return
    
    if plus:
        dfs(depth + 1, total + nums[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - nums[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * nums[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, total // nums[depth], plus, minus, multiply, divide - 1)

dfs(1, nums[0], signs[0], signs[1], signs[2], signs[3])

print(maxNum)
print(minNum)

이 코드에서 depth가 1부터 시작한 이유는 nums의 첫 번째 값을 total에 미리 담아두고 시작하기 때문에 depth 0을 넘어갔다.