Algorithm/DFS & BFS

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

안드선생 2021. 4. 30. 16:20
반응형

www.acmicpc.net/problem/15658

 

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

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수

www.acmicpc.net

문제 설명

 

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


풀이 과정

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

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

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

반응형