[Python/Baekjoon] 14888. 연산자 끼워넣기

💬 문제

문제 난이도: 백준 실버 1

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

❗️접근 방법

1. 문제에서 조건으로 주어진 결과의 최솟값과 최댓값을 활용해 초기 MAXRESULT / MINRESULT를 설정한다.
2. 연산자들에게 고유의 숫자(0~3)을 부여하고 사용할 때 1을 빼주는 식으로 연산자 순열을 만든다.
3. 재귀를 호출할 때마다 depth += 1 해줘서 depth == N이 될 때,즉 N-1개의 연산자들로 새로운 순열이 만들어졌을 때 이전의 결과와 비교한다.

✅ 정답 코드

# 연산자 끼워넣기 #DFS인 이유: depth == N일 때까지 내려갔다 오니까
import sys
input = sys.stdin.readline
print = sys.stdout.write

N = int(input())
nums = list(map(int, input().split(' ')))
operators = list(map(int, input().split(' ')))
MAXRESULT = -1000000000
MINRESULT = 1000000000

def solution(depth, tmpResult):
    global MAXRESULT, MINRESULT
    if depth == N:
        MAXRESULT = max(tmpResult, MAXRESULT)
        MINRESULT = min(tmpResult, MINRESULT)
        return
    # nums[i]를 해버리면 순서가 안 지켜진다.
    for i in range(4):
        if operators[i] > 0:
            operators[i] -= 1
            if i == 0:
                solution(depth+1, tmpResult+nums[depth])
            elif i == 1:
                solution(depth+1, tmpResult-nums[depth])
            elif i == 2:
                solution(depth+1, tmpResult*nums[depth])
            else:
                if tmpResult < 0:
                    solution(depth+1, -(-tmpResult//nums[depth]))
                else:
                    solution(depth+1, tmpResult//nums[depth])

            operators[i] += 1

solution(1, nums[0])
print(f'{MAXRESULT}\n{MINRESULT}')

✍️ 미처 생각하지 못했던 부분

• 문제에서 주어진 숫자들의 순서를 바꿀 수 없다. 위 문제에서 순서를 바꾸며 최댓값과 최솟값을 갱신해주는 주체는 연산자이다.