백준 14888번 - 연산자 끼워넣기 python

문제 링크 : https://www.acmicpc.net/problem/14888


첫번째 예제 입력을 보면,
첫 째 줄에는 수의 개수는 2 ,
둘 째 줄에는 5 6
셋째줄에는 0 0 1 0 이기 때문에 곱셈이 하나 있다는 뜻이다.

그러면 출력의 결과는 최댓값, 최솟값 둘로 진행해야 하는데, 연산자가 하나밖에 없으니 둘다 30이라는 것이다.

—
다행인 점은, 첫번째 줄에 숫자의 크기를 준다는 점,
그리고 숫자들이 섞이지 않고 순서를 지킨다는 점.
최댓값과 최솟값의 값이 정해진 점

How to access?
Maybe brote forcing?
이걸 설마 하나하나 다해보는건 아니겠지 고민하다가
결국 알고리즘 분류 힌트를 봤는데,
브루트포스 알고리즘 이었다… 플러스로 백 트래킹

import sys
input = sys.stdin.readline

N = int(input())
number = list(map(int, input().split()))
cal = list(map(int, input().split()))

max_num = -1e9
min_num = 1e9

def dfs(depth, total, plus, mius, mult, divide):
    global max_num
    global min_num
    if depth == N:
        max_num = max(total, max_num)
        min_num = min(total, min_num)
        return 
    if plus:
        dfs(depth + 1, total +  number[depth], plus -1, mius, mult, divide)
    if mius:
            dfs(depth + 1, total -  number[depth], plus , mius - 1, mult, divide)
    if mult:
            dfs(depth + 1, total *  number[depth], plus, mius, mult -1, divide)
    if divide:
            dfs(depth + 1, int(total / number[depth]), plus, mius, mult, divide - 1)
            # 이거 // 하면 안됨, 그 이유 설명해서 적기
            
dfs(1, number[0], cal[0], cal[1], cal[2], cal[3])
print(max_num)
print(min_num)

신경써야 했던 것은
나눗셈이 정수 나눗셈으로 몫만 취한다는 것이다. 음수를 양수로 나눌 때, C++14의 기준으로, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것이 같게 해야한다.
그래서 나눗셈을 계산할 때에는
// 가 아닌, int()로 감싸주는 작업이 필요했다.


다른 사람들의 코드를 보니, 백트레킹인 DFS 방식으로가 가장 정석이었던 것 같다.
근데, 순열을 사용하여 BFS로 푸는 방법도 있다고 한다. 그 방법은 시간복잡도가 좋지 않다.