[백준] 14888 파이썬(python) : 연산자 끼워넣기 - (★)

14888번 : 연산자 끼워넣기

 

 

모든 값을 연산자를 넣고 구하는 방법으로 브루트포스와 백트래킹을 떠올릴 수 있다. 연산자는 +, -, x, / 이렇게 4가지가 전부이고 입력받는 수의 범위는 2 <= n <= 11 이니까 O(4ⁿ)이 복잡도가 된다. (4개 들어갈 수 있는데 그 길이가 n개다.) 

백트래킹 알고리즘 복잡도 구하는 법 : n x n x n x n x n x n x n x n = n^m  (n개의 방법이 m개 있다)

=> O(n^m)

그래서 문제에서 4^11 = 4,194,304이 되는데 제한시간 2초안에 들어올 수 있다.

 

import sys
n = int(sys.stdin.readline())
number = list(map(int, sys.stdin.readline().split()))
operator = list(map(int, sys.stdin.readline().split()))
maxAns = sys.maxsize * -1 #1
minAns = sys.maxsize

def backTracking(idx, sum): #2
    global maxAns, minAns
    if idx == n-1: #3
        minAns = min(minAns, sum) #9
        maxAns = max(maxAns, sum)
        return
    for i in range(4): #4
        tmp = sum #5
        if operator[i] == 0: continue #6
        if i == 0: sum += number[idx+1]
        elif i == 1: sum -= number[idx+1]
        elif i == 2: sum *= number[idx+1]
        else:
            if sum < 0: sum = (abs(sum)//number[idx+1])*-1 #8
            else: sum //= number[idx+1]
        operator[i] -= 1
        backTracking(idx+1, sum) #7
        operator[i] += 1
        sum = tmp #5

backTracking(0, number[0])
print(maxAns)
print(minAns)

 

#1 : sys모듈의 maxsize를 사용해서 최대값과 최소값을 구하는 변수 초기화

#2, 3, 4, 6, 7 : 백트래킹의 큰 틀을 이루는 코드들이다. 저번 포스팅에서 했던 15649번(N과 M (1))과 같다.

#5 : 끝까지 탐색한 후 원래 값으로 돌아오기 위한 코드

#8 : 파이썬음수 나누기 때문에 이렇게 else에서도 두개로 나눴다. 문제에서 "음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다." 라고 했기 때문에 이렇게 해준다.

다른 방법으로는 int(sum/number[index+1]) 이런 방법도 있다. 하지만 문제에서 하라는대로 구현하면 위의 방법이 더 직관적이다.

#9 : 둘중 더 큰값 또는 작은 값으로 바꿔주는 방법

 

 

 

---

15649번 : N과 M (1)

 

음수 나누기에 대하여

 

#8을 사용해야 하는 이유 : C++과 파이썬의 나머지 연산의 차이