[백준/14888] 연산자 끼워넣기 (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
op = list(map(int, input().split()))
minRes, maxRes = int(1e9), -int(1e9)
res = nums[0] # 첫번째 숫자 뒤 부터 연산자와 숫자가 나오기 때문

def dfs(idx):
    global res
    global minRes, maxRes

    if idx == n:
        if res < minRes:
            minRes = res
        if res > maxRes:
            maxRes = res
        return

    for i in range(4):
        temp = res
        if op[i] > 0:
            if i == 0:
                res += nums[idx]
            elif i == 1:
                res -= nums[idx]
            elif i == 2:
                res *= nums[idx]
            else:
                if res >= 0:
                    res //= nums[idx]
                else:
                # res가 음수일 경우 res를 양수로 바꿔 몫을 구한 후 다시 음수로 만든다
                    res = (-res // nums[idx]) * -1
                    
            op[i] -= 1
            dfs(idx + 1)
            res = temp
            op[i] += 1 # 백트래킹을 통해 원래 상태로 되돌린다

dfs(1)
print(maxRes)
print(minRes)

---

✔ 설명

순열과 dfs 방법으로 해결할 수 있다.

dfs로 idx 값에 맞는 연산자와 숫자를 계산해 res에 중첩해간다.

재귀 함수가 돌아가는 방법은 디버깅을 하면서 알 수 있다. 

---

✔ 후기

minRes, maxRes = int(1e9), -int(1e9)를 하지 않으면 값이 제대로 나오지 않는다.

최대 10억 최소 -10억이라는 범위가 있기 때문에 지정해주지 않으면 dfs 함수의 if idx == n 부분의 조건이 제대로 풀리지 않을 것이다. 

또한 div 경우에 음수, 양수 조건을 따져서 계산해주지 않으면 잘못된 값이 나올 수 있으니 해당 조건도 생략하지 않고 그대로 사용해야한다.

 

dfs로 푸는 문제인 것은 인지했으나 어떻게 재귀함수를 짜야하는지, 어떤 조건을 걸어야 재귀를 멈출 수 있고, 백트래킹으로 op를 다시 복구할 수 있을지 고민했다.

조건은 배열의 index 값으로 줄 수 있었고 백트래킹으로 op를 복구하는 방법은 op[i] += 1을 하면 되는 것이었다.

---

✔ 다른 코드

import sys
input = sys.stdin.readline


N = int(input())

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

a, b, c, d = map(int, input().split())

max_ans, min_ans = -sys.maxsize -1, sys.maxsize

def solution(num, idx, add, sub, mul, div):
    global max_ans, min_ans
    if idx == N:
        max_ans = max(max_ans, num)
        min_ans = min(min_ans, num)
        return 
    
    if add > 0:
        solution(num + nums[idx], idx + 1, add - 1, sub, mul, div)
    if sub > 0:
        solution(num - nums[idx], idx + 1, add, sub - 1, mul, div)
    if mul > 0:
        solution(num * nums[idx], idx + 1, add, sub , mul -1, div)
    if div > 0:
        solution(int(num / nums[idx]), idx + 1, add, sub, mul, div -1)


solution(nums[0], 1, a, b, c, d)
print(max_ans)
print(min_ans)