[Python][백준] 14888. 연산자 끼워넣기 / 브루트포스, 백트레킹 (S1)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

import sys

sys.setrecursionlimit(100000) 
input = sys.stdin.readline

N = int(input())
lst = list(map(int,input().split()))

add,sub,mul,div = map(int,input().split())

mx = -sys.maxsize
mn = sys.maxsize

def dfs(n,rs,add,sub,mul,div):
    global mn
    global mx

    if n == N:
        mn = min(rs,mn)
        mx = max(rs,mx)
        return 
    
    if add > 0 : dfs(n+1,rs+lst[n],add-1,sub,mul,div)
    if sub > 0 : dfs(n+1,rs-lst[n],add,sub-1,mul,div)
    if mul > 0 : dfs(n+1,rs*lst[n],add,sub,mul-1,div)
    if div > 0 : dfs(n+1,int(rs/lst[n]),add,sub,mul,div-1)

dfs(1,lst[0],add,sub,mul,div)

print(mx)
print(mn)

 

1. 숫자 리스트와, 연산자 리스트를 각각 받아준다.

 

2. 초기의 최대,최소 값을 설정해준다.

 

3. dfs 함수를 만들어준다.

- 각각 add/sub/mul/div를 조건문으로 실행 시켜준다. 

 

(나는 이 방법이 신기했다.  for 문이 아닌 if 문을 통해 구하는게 새로운 느낌이다.)

 

 

🔗  내 풀이

import sys
sys.setrecursionlimit(100000) 
input = sys.stdin.readline
N = int(input())
lst = list(map(int,input().split()))
operations_lst = list(map(int,input().split()))
operations = []

for n,op in zip(operations_lst,["+","-","*","%"]):
    operations += [op] * n
    

def concat(op):
    ls = []
    for i in range(len(lst)):
        ls.append(lst[i])
        if i == len(lst)-1 : break
        ls.append(op[i])
    return ls

def calcul(ls):
    ot = ls[0]
    for i in range(1,len(ls),2):        
        if ls[i] == '-' :
            ot -= ls[i+1]
        elif ls[i] == '+':
            ot += ls[i+1]
        elif ls[i] == '*':
            ot *= ls[i+1]
        elif ls[i] == '%':
            ot /= ls[i+1]
            ot = int(ot)
    return ot

rs = []
visited = [0] * N 
cnt = 0 
mn = 1e10
mx = 0

def combi(n):
    global mn
    global mx

    if n == N-1 : 
        ls = concat(rs)
        v = calcul(ls)
        mn = min(v,mn)
        mx = max(v,mx)
        return
    
    for i in range(N-1) : 
        if visited[i] == 0 :
            visited[i] = 1 
            rs.append(operations[i])
            combi(n+1)
            rs.pop()
            visited[i] = 0 

combi(0)
print(mx)
print(mn)

 

내 풀이는 너무 미친 짓이였다 ... 너무 복잡하게 생각했던 것 같다. 

 

간단하게 코드에 대해 설명하자면,  

concat 함수는 숫자 리스트와 연산자 리스트를 합쳐주는 함수이다.

그리고 calcul 함수를 통해 합쳐진 숫자,연산자 리스트를 계산한다.

 

이것들은 combi 함수에서 실행되고, 

combi 함수에서는 연산자 리스트들의 조합을 만들어준다.

 

마지막에 if 조건에 맞으면 mn과 mx를 초기화 해준다.

 

흠... 시간초과가 떴지만, 그래도... 예제에 있는 코드는 맞았다...

근데 좋은 풀이는 절대 아니다... 

 

문제에서 굳이 숫자와 연산자를 나눠서 준 이유를 생각해보자 !! 

 

📌 문제 코멘트 

저렇게 if 문 여러개로 재귀를 할 수 있다는 방식을 꼭 꼭 기억해두자 !!

---

📚문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

예제 입력 1 복사

2
5 6
0 0 1 0

예제 출력 1 복사

30
30

예제 입력 2 복사

3
3 4 5
1 0 1 0

예제 출력 2 복사

35
17

예제 입력 3 복사

6
1 2 3 4 5 6
2 1 1 1

예제 출력 3 복사

54
-24