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

문제 설명

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

14888번: 연산자 끼워넣기

주어진 숫자와 연산자로 만들 수 있는 수식의 결과값 중 최대값과 최소값을 구하면 됩니다.

---

풀이 과정

이 문제는 DFS와 백트래킹을 이용했다.

 

문제에서 연산에 사용할 숫자(A1,A2...An)와 연산자의 개수(b1, b2, b3, b4)가 주어진다.

연산자는 앞에서 부터 차례대로 더하기, 빼기, 곱하기, 나누기 연산자의 개수를 나타낸다

숫자의 순서는 바뀌면 안되며, 연산자의 순서만을 바꿀 수 있다.

 

따라서, 숫자의 순서는 유지한채 연산자를 더하기, 빼기, 곱하기, 나누기를 써가며 식을 바꿔주면 되므로

첫 번째 숫자에 첫 연산자를 넣고 DFS를 돌린다음

다시 백트래킹을 통해 원래 상태로 돌린 후

두 번째 연산자를 넣고 DFS를 돌린다음 다시 백트래킹으로 원래 상태로 돌려

모든 경우의 수를 찾아내야 한다.

 

그리고 이 모든 경우의 수 중에 최댓값과 최솟값을 찾아 출력하면 된다.

이를 파이썬 코드로 나타내면 다음과 같다.

n = int(input())
number = list(map(int, input().split()))
op = list(map(int, input().split()))
minR = int(1e9)
maxR = -int(1e9)

answer = number[0]

def dfs(idx):
    global answer
    global minR, maxR

    if idx == n:
        if answer > maxR:
            maxR = answer
        if answer < minR:
            minR = answer
        return

    for i in range(4):
        tmp = answer
        if op[i] > 0:
            if i == 0:
                answer += number[idx]
            elif i == 1:
                answer -= number[idx]
            elif i == 2:
                answer *= number[idx]
            else:
                if answer >= 0:
                    answer //= number[idx]
                else:
                    answer = (-answer // number[idx]) * -1

            op[i] -= 1
            dfs(idx+1)
            answer = tmp
            op[i] += 1


dfs(1)
print(maxR)
print(minR)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !