백준 14888번: 연산자 끼워넣기

import sys

input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))  # +, -, *, //

maximum = -1e9
minimum = 1e9


def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return

    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(maximum)
print(minimum)

이 문제는 주어진 숫자와 연산자를 이용해 만들 수 있는 모든 가능한 수식을 탐색하여 최대값과 최소값을 구하는 문제입니다. 이를 해결하기 위해 깊이 우선 탐색(DFS)을 사용합니다.

 

• 완전 탐색 필요: 문제에서 요구하는 것은 가능한 모든 조합을 탐색하여 최대값과 최소값을 찾는 것입니다. DFS는 이러한 완전 탐색에 적합한 방법입니다.
• 재귀적 접근: DFS는 재귀적 접근을 사용하여 문제를 해결합니다. 각 단계에서 가능한 모든 선택지를 시도하고, 이를 통해 다음 단계로 재귀적으로 넘어가면서 모든 조합을 탐색합니다.
• 백트래킹: DFS는 백트래킹을 통해 불필요한 경로를 가지 않고 효율적으로 탐색할 수 있습니다. 모든 가능한 연산자 배치를 시도하고, 연산자가 소진되면 되돌아가 다른 경로를 탐색합니다.

 

1. 입력으로 숫자의 개수 N, 숫자 리스트 num, 연산자 리스트 op를 받습니다.
2. 최대값과 최소값을 매우 작은 값과 큰 값으로 초기화합니다.
3. DFS 함수는 현재 깊이, 현재까지의 계산 결과, 남은 연산자의 개수를 매개변수로 받습니다.
   • 현재 깊이가 숫자의 개수 N과 같으면, 모든 숫자를 사용한 것이므로 계산 결과를 최대값과 최소값과 비교하여 갱신합니다.
   • 각 연산자가 남아 있는 경우, 해당 연산자를 사용하여 다음 깊이로 재귀 호출을 합니다.
4. 첫 번째 숫자와 초기 연산자 개수를 사용하여 DFS 탐색을 시작합니다.
5. 모든 탐색이 끝난 후, 최대값과 최소값을 출력합니다.