알고리즘 백준 14888 연산자 끼워넣기(파이썬)

알고리즘 백준 14888 연산자 끼워넣기(파이썬)

백준 연산자 끼워넣기 파이썬

백준 파이썬 연산자 끼워넣기

 

 

문제

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억보다 작거나 같다.

 

코드

 

def backtracking(minmaxNum,idx):
    if sum(math) ==0:   #1)   #math는 연산자의 개수를 나타내는 것인데 이게 0이라는소리는 연산자를 다 사용하였다는 뜻 즉 계산이 끝남
        minmaxList.append(minmaxNum)
        return minmaxNum

    for i in range(len(math)):  #연산자의 길이만큼 for문을 돈다 
        if math[i] ==0 :  2)  #해당 연산자가 없으면 다음 연산자로 
            continue
            
        upNum = minmaxNum 3)  #해당 변수가 필요한 이유는 minmaxNum이라는 변수를 계속 재귀로 돌리는데 그렇게되면 상위 재귀에서 minmaxNum의 숫자가 바뀌어서 따로 저장하는 부분이 필요
        if i==0:
        
            minmaxNum += number[idx+1]
        if i==1:
        
            minmaxNum -= number[idx+1]
        if i==2:
        
            minmaxNum *= number[idx+1]
        if i==3:   #나누기인데 음수면 양수로 바꿧다가 그 몫을 음수로
        
            if minmaxNum >=0:
                minmaxNum = minmaxNum // number[idx+1]
                
            else:
                minmaxNum = -(abs(minmaxNum) // number[idx+1])


        math[i] = math[i] -1  4)
        backtracking(minmaxNum,idx+1)
        math[i] = math[i] +1
        minmaxNum =upNum


#
#
#
if __name__ == '__main__':
    import sys

    N = int(sys.stdin.readline())
    #  print(3//6)
    #  print(-3//6)
    number = list(map(int, sys.stdin.readline().split()))
    math = list(map(int, sys.stdin.readline().split()))
    minmaxList =[]
    backtracking(number[0],0)
    print(max(minmaxList))
    print(min(minmaxList))

 

 

코드설명

 0) 함수  backtracking의 파라미터로 처음 최대최솟값인 number[0] , number의 인덱스 번호를 확인하기 위한  idx를 받아야한다 - 그래야 재귀를 돌때마다 number의 다음 숫자로 갈 수 있다

0-1) 연산자를 기준으로 계산을 수행한다 , 연산자가 0일경우에는 다음 연산자를 확인한다

 

0-2) 해당 연산자의 계산이 끝나면 연산자의 숫자를 줄여주며 다시 backtracking함수를 재귀로 부르고 해당 재귀가 끝나면 해당 연산자를 다시 더해준다     -> 그래야 처음 minmaxNum값이 3이라고하고 다음 숫자가 4라고하면 1)3+4 , 2)3-4 ,   3) 3*4 ,    4)  3%4  의 모든 경우의 연산이 가능하다

 

 

1) 연산자의 개수가 0이라는 소리는 계산이 끝났다는 의미이므로 minmaxNum을 최대 최소를 구하는 리스트에 추가한다

 

2) 연산자의 길이만큼(+,-,*,%) for문을 도는데 해당 연산자가 0이면 (연산자가없으면) 다음 연산자로 넘어간다

 

3) upNum이라는 변수가 필요한 이유는 재귀를 돌리다보면  minmaxNum이 자식의 minmaxNum값과 혼용되어 제대로 연산이 되지 않아 해당 함수에서 minmaxNum을 따로 저장하는 변수를 추가하였다

 

4) 연산자를 하나 사용하면 빼주고 다른 경우의 수를 탐색해야하기때문에 backtracking함수를 부르며

   해당 재귀가 끝나면 연산자를 다시 추가해준다 -> 그래야지 모든 경우의 수 탐색이 가능하다

   또한 마지막에 다시 minmaxNum을 해당 부분에서 저장한 upNum값을 주어 혼용이 일어나지 않게 하였다.

 

 

 

깃허브

https://github.com/developer-hyun/Algorithm-Study/tree/main