[#14888] 연산자 끼워넣기

RookieAND·2022년 8월 24일

백준 백트래킹 코테

BaekJoon

목록 보기

29/42

❓ Question

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

📖 Before Start

백트래킹을 사용하여 최대 / 최솟값을 도출해내는 문제였다.

이번 문제는 백트래킹을 활용하여 계산 결과의 최대, 최솟값을 구해야 했다.
백트래킹에 대한 이해도가 아직 부족해서인지, 알고리즘을 쉽게 떠올리지 못했다.

✒️ Design Algorithm

처음엔 주어진 연산자를 활용하여 순열 을 제작하고자 했다.

숫자 N 개와 연산자 N-1 개가 있고, 주어진 숫자들의 위치는 전부 고정되어 있다.
이 말인 즉슨, 숫자 사이에 들어가는 연산자의 위치만 조정하여 수식을 만든다는 뜻인데..

여기서 나는 주어진 연산자들을 N-1 길이의 순열로 조합하여 케이스를 분석하려 했다.
물론 백트래킹을 쓰는 방법도 있겠지만 정말 슬프게도 방법이 잘 떠오르지 않았다.

💻 Making Own Code

✅ Correct Code (Using Permutations)

import sys
from math import inf
from itertools import permutations

read = sys.stdin.readline
N = int(read())
numbers = list(map(int, read().split()))

# 사용 가능한 연산자 목록을 하나의 List에 담는다.
add, sub, mul, div = list(map(int, read().split()))
operator_list = ['+'] * add + ['-'] * sub +  ['*'] * mul + ['/'] * div

MAX, MIN = -inf, inf

# N - 1 개의 연산자로 순열을 만들고, 각각의 케이스를 조사한다. 
for case in permutations(operator_list, N - 1):
    result = numbers[0]
    for idx in range(1, N):
        if case[idx - 1] == '+':
            result += numbers[idx]
        if case[idx - 1] == '-':
            result -= numbers[idx]
        if case[idx - 1] == '*':
            result *= numbers[idx]
        if case[idx - 1] == '/':
            result = int(result / numbers[idx])

    MAX = max(result, MAX)
    MIN = min(result, MIN)

print(MAX)
print(MIN)

정답 처리를 받은 코드긴 하다. 하지만 백트래킹 을 사용하지 않았고 효율이 좋지 않다.

순열로 문제를 접근한 건 좋았지만, 시간과 메모리 측면에서 모두 성능이 떨어졌다.
따라서 외부의 힘을 빌려 백트래킹으로 문제를 푸는 코드를 공부하여 다시 제출하였다.

✅ Correct Code (Using Back-Tracking)

import sys
from math import inf

read = sys.stdin.readline
N = int(read())
numbers = list(map(int, read().split()))
oper_num = list(map(int, read().split()))

MAX, MIN = -inf, inf

def dfs(dep, result, add, sub, mul, div):
    global MAX, MIN
    if dep == N:
        MAX = max(result, MAX)
        MIN = min(result, MIN)
        return

    if add:
        dfs(dep + 1, result + numbers[dep], add - 1, sub, mul, div)
    if sub:
        dfs(dep + 1, result - numbers[dep], add, sub - 1, mul, div)
    if mul:
        dfs(dep + 1, result * numbers[dep], add, sub, mul - 1, div)
    if div:
        dfs(dep + 1, int(result / numbers[dep]), add, sub, mul, div -1)

dfs(1, numbers[0], oper_num[0], oper_num[1], oper_num[2], oper_num[3])
print(MAX)
print(MIN)