백준 14888 : 연산자 끼워넣기 (파이썬)

연산자 끼워넣기

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

---

풀이 코드

# https://teching.tistory.com/
import sys

n = int(sys.stdin.readline().rstrip())
nums = list(map(int,sys.stdin.readline().split()))
#operator  0: +, 1: -, 2: *, 3: /
operator = list(map(int,sys.stdin.readline().split()))
use_operator = [0, 0, 0, 0]
answerMax = -1000000000
answerMin = 1000000000
def solve(idx,res):
    global n, answerMin, answerMax
    if idx == n:
        answerMin = min(answerMin, res)
        answerMax = max(answerMax, res)
        return
    for i in range(4):
        if operator[i]>use_operator[i]:
            if i == 0:
                tmp = res+nums[idx]
            elif i == 1:
                tmp = res-nums[idx]
            elif i == 2:
                tmp = res*nums[idx]
            elif i == 3:
                tmp = (res//nums[idx]) if res>=0 else -(-res//nums[idx])
            use_operator[i] += 1
            solve(idx+1, tmp)
            use_operator[i] -= 1

solve(1,nums[0])
print(answerMax)
print(answerMin)

해설

각 연산을 다 한번씩 확인하여 사용하지 않은 연산자를 하나씩 넣어가면서 모든 경우의 수를 확인하는 백트래킹 알고리즘을 이용해 문제를 풀이하였다. 나는 DFS를 통해 완전 탐색을 진행하였다.

즉, DFS에 대한 개념만 있다면 그리 어렵지 않게 풀이할 수 있는 문제!!

DFS(깊이우선탐색)에 관한 내용은 https://teching.tistory.com/83에 정리를 해둔 것이 있으니 참고!!

깊이 우선 탐색

연산자를 얼만큼 사용했는지 확인하는 방법

입력의 세번째 줄에 각 연사자들 ( +, -, *, / )의 개수가 입력된다.

이를 배열에 저장하여 백트래킹을 진행하며 만약 해당 연산자를 사용하였을 경우 해당 연산자의 개수를 한 개 줄여준다.

그 후 다음 연산자를 넣어보고... 이런 방법으로 끝까지 도달했을때(모든 연산자를 하나씩 넣었을 때)의 모든 경우를 구해서 최댓값, 최솟값을 구해주었다.

그리고 끝까지 도달한 뒤 다시 되돌아올때 다시 해당 연산자의 개수를 다시 하나 늘려주는 방법으로 구현을 하였다.