[n15686] 연산자 끼워넣기(2) in python

---

초기 max값은 1 * 1e9

초기 min값은 -1*1e9

 

 

이 문제는 백트래킹 개념을 사용하면 풀 수 있다.

 

 

for문을 돌려서 해야하나 잠시 고민했는데

재귀함수만 이용해도 충분히 가능했던 문제!

(아직 재귀함수 사용하는 게 서투른 편..)

 

+ , - , * , / 순으로 if문 작성

 

 

(주의해야 할 부분)

또, 나눗셈은 정수 나눗셈으로 몫만 취한다.

음수를 양수로 나눌 때는 C++14의 기준을 따른다.

즉, 양수로 바꾼 뒤 몫을 취하고,

그 몫을 음수로 바꾼 것과 같다.

 

나는 temp가 음수일 때, 양수일때를 나눠서

처리해줘야하는 줄 알았다.

 

그러나 파이썬 연산자만 잘 활용해도

충분히 간단하게 풀 수 있었다.

 

 

파이썬 연산자에서

나눗셈을 담당하는 연산자는

총 3가지

 

1. /

: 나누기

 

2. //

: 나누기 연산 후

소수점 이하의 수를 버리고, 정수 부분의 수만 구함

 

3. %

나누기 연산 후 몫이 아닌 나머지를 구함

 

 

a/b를 나눈 수 int형으로 변환시켜주면

손쉽게 답을 도출해낼 수 있다!

 

예시)

13/4 -> 3.25

-13/4 -> -3.25

- 13//4 -> -4

int(13/4) -> 3

int(-13/4) -> -3

n = int(input())
array = list(map(int, input().split()))
operator = list(map(int, input().split()))
maxResult = -1000000000
minResult = 1000000000


def dfs(idx, temp):
    global maxResult, minResult
    if idx == n-1:  # 연산자를 사이사이에 다 끼워넣었을 경우
        minResult = min(minResult, temp)
        maxResult = max(maxResult, temp)
        return
    if operator[0] > 0:  # +
        operator[0] -= 1
        dfs(idx + 1, temp + array[idx+1])
        operator[0] += 1
    if operator[1] > 0:  # -
        operator[1] -= 1
        dfs(idx + 1, temp - array[idx+1])
        operator[1] += 1
    if operator[2] > 0:  # *
        operator[2] -= 1
        dfs(idx + 1, temp * array[idx+1])
        operator[2] += 1
    if operator[3] > 0:  # //
        operator[3] -= 1
        dfs(idx + 1, int(temp / array[idx+1]))
        operator[3] += 1


dfs(0, array[0])
print(maxResult)
print(minResult,end='')

'''
+ - X // 2 3 1 2 
+ dfs(+ : 1, - : 3, x :1 ,// :2)
    + dfs(+:0, - : 3, x :1 ,// :2)
        - dfs (+:0, - : 2, x :1 ,// :2)
         - dfs (+:0, - : 1, x :1 ,// :2)
          - dfs(+:0, - : 0, x :1 ,// :2)
            * dfs(+:0, - : 1, x :1 ,// :2)
              dfs(+:0, - : 1, x :0 ,// :2)
              * dfs(+:0, - : 3, x :1 ,// :1)
'''