Algorithm/DFS & BFS
[백준] 15658 연산자 끼워넣기 2 (Python 파이썬)
안드선생
2021. 4. 30. 16:20
반응형
문제 설명
주어진 숫자와 연산자로 만들 수 있는 수식의 결과값 중 최대값과 최소값을 구하면 됩니다.
풀이 과정
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)
전체 문제 & 코드는 위의 깃에 정리되어 있습니다.
팔로우 & 맞팔은 환영입니다 !
반응형