문제 출처 : https://www.acmicpc.net/problem/14888

문제 파악

nums의 순서는 바꿀 수 없지만 operator를 잘 활용해서 만들 수 있는 결과의 최댓값과 최솟값을 각각 print() 해야 한다.

수의 개수가 최대 11
그렇다면 연산자가 들어갈 수 있는 곳은 최대 10곳
연산자가 4종류이니 총 경우의 수 = 4^10 (약 백만)
완전탐색이 가능한 수이다. (1억정도까지 가능)

"식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다."
=> DFS하며 안될때마다 백트래킹?

해답 및 풀이

import sys
input = sys.stdin.readline


# 입력 
    # 수의 개수 N (2 <= N <11)
N = int(input())
    # 수 A1,A2...An
nums = list(map(int,input().split()))
    # N-1개의 연산자 | 덧셈, 뺄셈, 곱셈, 나눗셈 | 의 개수
plus, minus, mul, div = map(int,input().split())


# --- --- --- --- --- --- --- --- --- --- --- --- ---

# nums의 순서는 바꿀 수 없지만 operator를 잘 활용해서 만들 수 있는 결과의 최댓값과 최솟값을 각각 print() 해야 한다.
# 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 떄문에 백트래킹으로 DFS?

# 문제에서 제시한 최대,최소의 범위
max_val = +1e9
min_val = -1e9

def dfs(idx, acc, p, m, t, d):
    # idx: 다음에 사용할 피연산자 인덱스
    # acc: 지금까지의 누적 값
    # p,m,t,d : +,-,*,/ 개수

    global max_val,min_val
    
    if idx == N:
        max_val = max(min_val,acc)
        min_val = min(max_val,acc)
        return
    
    x = nums[idx] # x : nums값

    if p > 0:
        dfs(idx + 1, acc + x, p - 1, m, t, d)
    if m > 0:
        dfs(idx + 1, acc - x, p, m - 1, t, d)
    if t > 0:
        dfs(idx + 1, acc * x, p, m, t - 1, d)
    if d > 0 and x != 0:
        # 파이썬의 //는 음수 처리 방식이 다르므로 int(a / b)로 0 방향 절삭
        dfs(idx + 1, int(acc / x), p, m, t, d - 1)

dfs(1,nums[0],plus,minus,mul,div)

print(max_val)
print(min_val)

헷갈렸던 부분

    if p > 0:
        dfs(idx + 1, acc + x, p - 1, m, t, d)
    if m > 0:
        dfs(idx + 1, acc - x, p, m - 1, t, d)
    if t > 0:
        dfs(idx + 1, acc * x, p, m, t - 1, d)
    if d > 0 and x != 0:
        # 파이썬의 //는 음수 처리 방식이 다르므로 int(a / b)로 0 방향 절삭
        dfs(idx + 1, int(acc / x), p, m, t, d - 1)

에서 처음엔 plus가 남아 있는데 m부터 하는 경우가 없어 보였다.

만약 if가 아닌 elif였다면 한 가지만 타고 끝났을 것이다.
하지만 if들은 모두 독립적으로 실행된다.
즉, 재귀 한 단계 안에서
if p>0 가지를 먼저 깊게 탐색하고 돌아온 뒤,
같은 스택 프레임에서 바로 이어서 if m>0을 타기때문에
p를 쓰지 않고 m을 쓰는 경우도 다 탐색이 된다.