백준(baekjoon) 14888번: 연산자 끼워넣기(실버 1, 파이썬 PYTHON) - 백트래킹

문제

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개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 

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

14888번: 연산자 끼워넣기

 

import sys

N=int(sys.stdin.readline())
N_list=list(map(int,sys.stdin.readline().split()))
operator_list=list(map(int,sys.stdin.readline().split()))
max=-1000000000 
min=1000000000 
calculate=N_list[0]  

def dfs(num):
  global N,N_list,operator_list,max,min,calculate
  if(num==N): 
    if(max<calculate):  
      max=calculate 
    if(min>calculate): 
      min=calculate 
  else: 
    for x in range(4):
      if(operator_list[x]!=0):  
        if(x==0): 
          calculate+=N_list[num]  
          operator_list[x]-=1 
          dfs(num+1) 
          operator_list[x]+=1  
          calculate-=N_list[num] 
        if(x==1):  
          calculate-=N_list[num]
          operator_list[x]-=1
          dfs(num+1)
          operator_list[x]+=1
          calculate+=N_list[num]
        if(x==2):  
          calculate*=N_list[num]
          operator_list[x]-=1
          dfs(num+1)
          operator_list[x]+=1
          calculate//=N_list[num]
        if(x==3): 
          save=calculate
          calculate=int(calculate/N_list[num])
          operator_list[x]-=1
          dfs(num+1)
          operator_list[x]+=1
          calculate=save
        
dfs(1)
print(max)
print(min)

 

※ 백트래킹

 

 

● 먼저 N_list 배열에 입력되는 수를 저장 operator_list 배열에 각 연산자의 개수를 저장한다.

 

● max에는 가능한 가장 작은 값인 -10억을, min에는 가능한 가장 큰 값은 10억을 저장하고, calculate의 초기값으로는 N_list의 첫요소를 저장한다.(모든 계산은 무조건 N_list의 첫 요소부터 시작하기 때문!)

 

● 함수 dfs()의 매개변수의 값은 calculate의 값이 나오는데에 영향을 끼친 N_list 배열 요소의 수를 나타낸다. (calculate에는 현재 N_list 첫 요소 하나의 숫자가 영향을 미치고 있으므로 처음에는 dfs(1)을 호출하게 된다.)

 

● 만약 매개변수 num의 값이 N과 같고 최종 결과값 calculate가 max보다 크면 max를 결과값으로, 또 min보다 작으면 min을 결과값으로 각각 갱신해준 뒤 함수는 끝나게된다.

 

● 매개변수의 값이 N보다 작으면 각 operator_list배열의 요소들을 살펴본다.

 

● operator_list요소를 차례대로 살피며 각 요소가 0이 아니고

그 요소의 인덱스가 0이면 

-> calculate값에 N_list[num], 즉 현재 calculate 값에 영향을 미치고 있는 수의 다음수를 더해주고

-> 덧셈 연산자의 개수를 하나 줄여준 뒤

-> 이제 calculate 값에 영향을 미치는 수가 하나 늘었으므로 dfs(num+1)을 호출해준다.

-> 마지막으로 연산자의 개수를 하나 줄여주었으므로 다시 원래 값으로 되돌리기 위해 하나 증가시키고

-> calculate값에 N_list[num] 값이 더해졌으므로 다시 원래 값으로 되돌리기 위해 N_list[num]값을 다시 빼준다.

 

그 요소의 인덱스가 1이면 

-> calculate값에 N_list[num], 즉 현재 calculate 값에 영향을 미치고 있는 수의 다음수를 빼주고

-> 뺄셈 연산자의 개수를 하나 줄여준 뒤

-> 이제 calculate 값에 영향을 미치는 수가 하나 늘었으므로 dfs(num+1)을 호출해준다.

-> 마지막으로 연산자의 개수를 하나 줄여주었으므로 다시 원래 값으로 되돌리기 위해 하나 증가시키고

-> calculate값에 N_list[num] 값이 빼졌으므로 다시 원래 값으로 되돌리기 위해 N_list[num]값을 다시 더해준다.

 

● 그 요소의 인덱스가 2이면 

-> calculate값에 N_list[num], 즉 현재 calculate 값에 영향을 미치고 있는 수의 다음수를 곱해주고

-> 곱셈 연산자의 개수를 하나 줄여준 뒤

-> 이제 calculate 값에 영향을 미치는 수가 하나 늘었으므로 dfs(num+1)을 호출해준다.

-> 마지막으로 연산자의 개수를 하나 줄여주었으므로 다시 원래 값으로 되돌리기 위해 하나 증가시키고

-> calculate값에 N_list[num] 값이 곱해졌으므로 다시 원래 값으로 되돌리기 위해 N_list[num]값을 다시 나누어준다.

 

● 그 요소의 인덱스가 3이면 

-> calculate값에 N_list[num], 즉 현재 calculate 값에 영향을 미치고 있는 수의 다음수를 나누어주고

-> 나눗셈 연산자의 개수를 하나 줄여준 뒤

-> 이제 calculate 값에 영향을 미치는 수가 하나 늘었으므로 dfs(num+1)을 호출해준다.

-> 마지막으로 연산자의 개수를 하나 줄여주었으므로 다시 원래 값으로 되돌리기 위해 하나 증가시키고

-> calculate값에 N_list[num] 값이 나누어졌으므로 다시 원래 값으로 되돌리기 위해 N_list[num]값을 다시 곱해준다.

 

● 위의 과정을 모두 거친후 max와 min 값을 각각 출력해주면 답을 구할 수 있다~!!!

 

 

결과