[백준] 연산자 끼워넣기

문제

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

TC

나올 수 있는 연산자의 조합 과정이 시간복잡도가 된다.
O(99! / a!b!c!d!)

Idea

덧셈, 뺄셈, 곱셈, 나눗셈의 갯수가 남아 있다면 dfs를 재귀 호출하였다.
이때 if ~ elif 문이 아니라 각각의 갯수를 따져주어야 하기 때문에
4개의 if문을 사용해야 하는 것이 핵심 아이디어라고 생각한다.

code (Python)

# 입력 값
n = int(input())
nums = list(map(int, input().split()))
# + 개수, - 개수, * 개수, // 개수
op = list(map(int, input().split()))

# 최댓값
max_value = -int(1e9)
# 최솟값
min_value = int(1e9)

def dfs(depth, total, plus, minus, multiply, divide):
    global max_value, min_value

    # 연산자의 개수만큼 dfs 탐색을 했다면
    # 최댓값과 최솟값 구하고 리턴하기
    if depth == n:
        max_value = max(max_value, total)
        min_value = min(min_value, total)
        return

    if plus:
        dfs(depth+1, total + nums[depth], plus-1, minus, multiply, divide)
    if minus:
        dfs(depth+1, total - nums[depth], plus, minus-1, multiply, divide)
    if multiply:
        dfs(depth+1, total * nums[depth], plus, minus, multiply-1, divide)
    if divide:
        dfs(depth+1, int(total / nums[depth]), plus, minus, multiply, divide-1)

dfs(1, nums[0], op[0], op[1], op[2], op[3])
print(max_value)
print(min_value)

self code review

이 문제를 보고 아 이건 dfs다! 라고 생각해서 바로 dfs로 풀었다.

다른 사람들의 코드를 보다가 순열 라이브러리와 bfs로 풀이한 것을 보게 되었다.
연산자의 기호들을 차례대로 받아 순열을 이용해 가능한 모든 경우의 수를 계산하여 큐에 삽입해서 푼 풀이 같았다. (예를 들어, '+', '-', 'x', '%' 4가지 연산자가 있다면 24가지(=4!) 경우릐 수를 모두 비교함)

순열을 이용해 풀면 쉽게 풀 수는 있지만, 시간 복잡도가 많이 소요돼서 python3에서는 시간초과가 뜬다고 한다.

사실, 순열까지는 생각을 못했고 보자마자 dfs가 떠올라서 푼 것이기는 하지만, 어쩌면 시간 복잡도가 낮게 모범 답안으로 풀은 것 같다.

내 풀이는 아니지만, 다른 사람의 풀이 시간 비교를 가져와서 보면 다음과 같다.

사진을 보면 순열 라이브러리 + bfs 풀이와 dfs 풀이의 소요 시간 차이가 꽤나 큰 것을 알 수 있다.

reference

위 사진을 가져온 블로그의 주소를 첨부하고자 한다.

https://data-flower.tistory.com/72