[Python/코테] 백준 14888 연산자 끼워넣기

14888 연산자 끼워넣기

문제 및 조건 설명: https://www.acmicpc.net/problem/14888

알고리즘 설계

💡idea.

모든 연산을 수행해보아야 답을 알 수 있다. 그러나 최대와 최소만 구하면 되기 때문에, 지금까지의 최대/최소보다 작거나/크면 해당 경우의 수 연산을 멈추는 백트래킹 알고리즘을 활용할 수 있다.

 

2023.11.20 - [Algorithm] - [C++/코테] 백트래킹: 백준 15649, 9663, 1182

[C++/코테] 백트래킹: 백준 15649, 9663, 1182

 

🎲step.

1. 숫자의 순서는 그대로 두고, 연산자의 순서(조합)을 바꾼다.

2. 각 단계별로, 특정 연산을 실행하는 경우와 실행하지 않는 경우 2가지로 나뉜다. 2가지 케이스에 따라 나뉘게 된다. 이에 dfs를 활용하여 여러 경우의 수를 시도해볼 수 있다.

 

알고리즘 구현

코드 출처: https://jominseoo.tistory.com/m/97

N = int(input())

lst = list(map(int, input().split()))

op = list(map(int, input().split()))

max_value = -1e9
min_value = 1e9

def dfs(n, temp) :
    global max_value, min_value
    
    # 종료 조건
    if n == N-1:
        max_value = max(temp, max_value)
        min_value = min(temp, min_value)
        return
     
    if op[0] != 0 : # 덧셈
        op[0] -= 1
        dfs(n+1, temp + lst[n+1])
        op[0] += 1 

    if op[1] != 0 : # 뺄셈
        op[1]-= 1
        dfs(n+1, temp - lst[n+1])
        op[1] += 1
    
    if op[2] != 0 : # 곱셈
        op[2] -= 1
        dfs(n+1, temp * lst[n+1])
        op[2] += 1
    
    if op[3] != 0 : #나눗셈
        op[3] -= 1
        dfs(n+1, int(temp/lst[n+1]))
        op[3] += 1

dfs(0, lst[0])
print(max_value)
print(min_value)

나다어

• 가능한 모든 경우를 실행해야 할 때, 효과적인 계산을 위해 가지치기를 하는 백트래킹 알고리즘을 활용할 수 있다.
  해당 문제에서는 모든 경우를 실행하는 방법으로 DFS를 활용했다.
• 음수 나눗셈을 위해 파이썬의 내장함수 int 를 활용할 수 있다. 그냥 몫 연산자(//)를 사용하면 내림이 된다. 그러나 int 함수를 활용하면 소수점을 버리게 된다.
  ex) >>> 303 // 4
  75
  >>> int(-303 / 4)
  -75
• 최소 범위가 -10억이기 때문에 max값이 음수가 될 수 있어, 0으로 초기화 해서는 안된다.