[BOJ] 연산자 끼워 넣기

문제

🥈[실버1] 14888 - 연산자 끼워넣기

풀이

문제를 읽어보면 숫자의 최대 개수가 11개임을 알 수 있다. 파이썬으로 알고리즘을 풀 경우 대부분 연산이 1억 번 내외로 일어나면 통과이다. 만약 최대 숫자 개수에서 모든 경우의 수를 계산한다고 단순하게 생각했을 때, 총 10^4개의 경우의 수가 생긴다. 이런 경우 알고리즘을 짤 때, 전체 탐색을 이용해서 알고리즘을 짜도 무관하다.

---

전체 탐색으로 알고리즘을 구현할 경우에, 재귀 함수를 이용해서 간단하게 구현 할 수 있다. 메모리를 효율 적으로 사용할 수 있는 방법이 있겠지만, 이번에 알고리즘을 짤 때는 미처 고려하지 못했다.( 문제를 푸는 데는 지장은 없다. )

아이디어는 다음과 같다.

 

1. max와 min을 global 변수로 지정한다.
2. 숫자를 담은 배열의 첫 번째와 두 번째의 숫자를 뽑아서 연산을 실행한 다음, 다시 배열에 넣는다.
3. 숫자가 1 개가 될 때 까지 2번을 반복한다.
4. 숫자가 1 개가 되면 global 변수의 min, max와 비교해서 업데이트 한다.
5. 1~4의 과정을 모든 경우에 대해서 연산한다.

코드

#연산자 끼워넣기 [Silver 1]  

import sys  
import copy  

def op(index,num1,num2):  
    if(index == 0):  
        return num1+num2  
    if(index == 1):  
        return num1-num2  
    if(index == 2):  
        return num1*num2  
    if(index == 3):  
        return int(num1/num2)  

def find(numbers, operators):  
    if(len(numbers) == 1):  
        global _max , _min  
        if(numbers[0]>_max):  
            _max = numbers[0]  
        if(numbers[0]<_min):  
            _min = numbers[0]  
        return  

 for i in range(4):  
        new_num = copy.deepcopy(numbers)  
        new_op = copy.deepcopy(operators)  
        num1 = new_num.pop(0)  
        num2 = new_num.pop(0)  
        if(new_op[i]>0):  
            new_op[i] = new_op[i]-1  
  new_num.insert(0,op(i,num1,num2))  
            find(new_num,new_op)  

n = int(sys.stdin.readline())  
number = list(map(int,sys.stdin.readline().split()))  
operators = list(map(int,sys.stdin.readline().split()))  
_max = (-1)*sys.maxsize  
_min = sys.maxsize  

find(number,operators)  

print(_max)  
print(_min)

알고리즘 분류

• 백트레킹
• 브루트포스 알고리즘