백준 15658 - 연산자 끼워넣기(2)

백준 15658 - 연산자 끼워넣기(2)

https://www.acmicpc.net/problem/15658

백트랙킹을 이용한 순열 문제 같다. 연산자 사용 횟수에 따라 연산자를 N-1개 뽑으면 된다. 주의 할 점은 나누기 할 때 주의해야한다.. 처음에 val //= A[idx+1]로 접근했더니 실패가 나왔다.. 정말 당황했다.. 손으로 계산까지 했는데 어디서 잘 못 됐는지 찾을 수 가 없었다... 나누기에서 문제가 발생한 것 같아서 val = int(val/ A[idx+1])해당 식을 통해 몫만 가져오니 통과했다....

N = int(input())
A = list(map(int,input().split()))
cnt = list(map(int,input().split()))
op = []
global max_val
max_val = -1000000001
global min_val
min_val = 1000000001

# 계산
def cal(op):
    val = A[0]
    for idx, i in enumerate(op):
        if i == 0:
            val += A[idx +1]
        elif i == 1:
            val -= A[idx +1]
        elif i == 2:
            val *= A[idx +1]
        elif i == 3:
            val = int(val/A[idx +1])
    return val

# 연산자 뽑기
def dfs(pick):
    global max_val
    global min_val
    #연산자는 N-1개 뽑기
    if pick == N-1:
        val = cal(op)
        min_val = min(min_val,val)
        max_val = max(max_val,val)
        return
    #0 = '+', 1 = '-', 2 = '*', 3 = '/'
    for i in range(4):
        if cnt[i] != 0:
            cnt[i] -= 1
            op.append(i)
            dfs(pick+1)
            op.pop()
            cnt[i] += 1

dfs(0)
print(max_val)
print(min_val)