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

www.acmicpc.net/problem/15658

15658번: 연산자 끼워넣기 (2)

문제 설명

 

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

---

풀이 과정

DFS의 백트래킹을 이용해서 풀어도 되고, 아래의 코드처럼 변수로 변하는 변수를 넘겨주어도 됩니다.

핵심은 주어진 숫자와 연산자로 조합할 수 있는 모든 경우의 수를 따져야 합니다.

 

백트래킹을 이용한 코드는

https://hongcoding.tistory.com/119 에 있습니다!

연산자 끼워넣기 1, 2 같은 방식으로 풀면 되므로 해당코드를 참고하셔도 좋습니다.

n = int(input())
num = list(map(int, input().split()))
plus, minus, mul, div = map(int, input().split())

mymax = int(-1e9)
mymin = int(1e9)

def dfs(index, result, plus, minus, mul, div):
    global mymax, mymin
    if index == n:
        mymax = max(mymax, result)
        mymin = min(mymin, result)
        return
    if plus > 0 :
        dfs(index + 1, result + num[index], plus-1, minus, mul, div)
    if minus > 0 :
        dfs(index + 1, result - num[index], plus, minus-1, mul, div)
    if mul > 0:
        dfs(index + 1, result * num[index], plus, minus, mul-1, div)
    if div > 0 :
        dfs(index + 1, int(result / num[index]), plus, minus, mul, div-1)


dfs(1, num[0], plus, minus, mul, div)
print(mymax)
print(mymin)

https://github.com/HongEunho

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

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