백준 14888 - 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

 

 

해당 문제는 모든 경우의 수를 탐색하는 브루트포스 탐색 알고리즘의 문제이다.

아직 DFS가 익숙하지 않아서 못 풀었다.

구글링을 해서 풀었는데 어떤 분의 풀이코드가 굉장히 깔끔해서 동일하게 작성해보고자 한다.

 

 

알고리즘 사고)

1. 재귀함수를 호출하여 풀이할 것이므로 DFS의 종료조건을 세워야 한다.

=> 입력받은 숫자를 차례대로 사용할 것이므로 입력받은 숫자가 모두 쓰이면 종료되는 것으로 하자.

=> 식을 사용할 때마다 깊이 depth 변수에 1을 더하고 해당 depth가 숫자의 갯수 n과  동일해지면 종료되는 것으로 하였다. 또한, 종료될 때마다 해당 값과 최대/최소값을 비교하여 최대/최소값을 갱신하도록 한다.

 

2. 연산자와 숫자가 연결될 때마다 값이 계속해서 계산된다.

=> total을 변수로 하여 인자로 계속 넘겨주며 연속적으로 계산될 수 있게끔 한다.

해당 total에 다음 숫자의  +, -, *, / 계산을 하면 된다.

 

3. 연산자의 갯수를 입력받으므로, 해당 연산자가 사용될 때마다 갯수를 1씩 줄여주며 인자로 넘긴다.

 

4. main에서 처음 DFS함수를 호출할 땐 인자로 depth = 0이 아닌  depth = 1로 넘겨주어야 한다.

=> 맨 처음 숫자를 넘겨주었기 때문에-

 

위 알고리즘을 적용한 풀이코드이다.

n = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))
a = -1e9
b = 1e9


def DFS(depth, total, plus, minus, multiply, divide):
    global a, b
    if depth == n:
        a = max(total, a)
        b = min(total, b)
    else:
        if plus:
            DFS(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
        if minus:
            DFS(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
        if multiply:
            DFS(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
        if divide:
            DFS(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


DFS(1, num[0], op[0], op[1], op[2], op[3])
print(a)  # 최대
print(b)  # 최소