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

문제

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

풀이

연산자를 하나씩 선택하여 수식을 만들어 나가는 문제
매 단계에서 남은 연산자들을 사용하여 가능한 모든 수식을 탐색해야 하므로 백트래킹을 활용하였습니다.
각 수식 결과를 계산하면서 현재까지의 최댓값과 최솟값을 갱신하면 됩니다.

문제를 보면 음수를 양수로 나눌 때는 C++14 기준을 따른다고 되어있습니다.
즉, 양수로 바꾼 뒤 몫을 취하고 그 몫을 음수로 바꾸어 주면 됩니다.
저는 이 부분 간과하고 문제를 풀었는데 이것 때문에 오답이 많이 나왔어요 🥲
문제를 잘 읽자..

코드

import sys
input = sys.stdin.readline

def dfs(idx, v, add, sub, mul, div):
    global mx, mn # 값을 갱신해야 되므로 전역 변수 선언

    if idx == n: # 인덱스 값이 n의 값과 같으면 mx, mn 갱신 후 리턴
        mx = max(mx, v)
        mn = min(mn, v)
        return
    
    if add > 0:
    	# 다음 연산을 진행해야 되므로 idx +1, 연산한 값, 연산자 -1
        dfs(idx + 1, v + arr[idx], add - 1, sub, mul, div)
    if sub > 0:
        dfs(idx + 1, v - arr[idx], add, sub - 1, mul, div)
    if mul > 0:
        dfs(idx + 1, v * arr[idx], add, sub, mul - 1, div)
    if div > 0:
        if v < 0: # 연산할 값이 음수일 때, 절대값 선언 후 나눈 다음 음수로 변환
            dfs(idx + 1, -(abs(v) // arr[idx]), add, sub, mul, div - 1)
        else:
            dfs(idx + 1, v // arr[idx], add, sub, mul, div - 1)


if __name__ == '__main__':
    n = int(input())
    arr = list(map(int,input().split()))
    add, sub, mul, div = map(int,input().split())
    
    # 정수형 선언 안 하면 오답처리 됩니다.
    mx = int(-1e9)
    mn = int(1e9)

    dfs(1, arr[0], add, sub, mul, div)

    print(mx)
    print(mn)