[백준 18428] 연산자 끼워넣기 (파이썬)

문제

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

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다.

예를 들어, 아래와 같은 식을 만들 수 있다.1+2+3-4×5÷61÷2+3+4-5×61+2÷3×4-5+61÷2×3-4+5+6식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.

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

 

 

---

 

 

문제풀이

 

접근방법: DFS를 사용한 재귀함수 호출이다

max값고 min값은 최소와 최대로 초기화를 시켜 놓아야한다.

 

나는 왜 

add+=1와 같이 dfs를호출한 후 더해주는지 이해가 가지 않았다..

add+=1를 해주는 이유는 원상복구! 가능한 연산자 수를 모두 계산해봐야하기 때문에 재귀 호출을 하고 원상복구 시켜 놓아서 여러가지의 경우의 수를 제한한다.

 

그리고 dfs함수를 만들 때, i, now를 받아서 한번에 처리하는 로직을 떠올리는데 어려움을 겪었던 것 같다.

dfs(1,data[0]) 이렇게 호출하는 것처럼 i는 1로 초기화를 하고 data[0]으로 now을 초기화 하여 계산을 효율적으로 하고 있다고 깨달았다

n=int(input())
data=list(map(int, input().split()))

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

max_value=-1e10
min_value=1e10

def dfs(i, now):
    global max_value, min_value, add, sub, mul, div
    if i==n:
        max_value=max(max_value, now)
        min_value=min(min_value, now)
    else:
        if add>0:
            add-=1
            dfs(i+1, now+data[i])
            add+=1
        if sub>0:
            sub-=1
            dfs(i+1, now-data[i])
            sub+=1
        if mul>0:
            mul-=1
            dfs(i+1, now*data[i])
            mul+=1
        if div>0:
            div-=1
            dfs(i+1, int(now/data[i]))
            div+=1

dfs(1, data[0])
print(max_value)
print(min_value)

 

재귀를 쓸 때는 dfs를 이용하자!