[백준] 14888 연산자 끼워넣기 Python3 DFS

이거 보자마자 생각난 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

 

n = int(input())
arr = list(map(int,input().split()))

plus, minus, cross, div = list(map(int,input().split()))

max_ = - int(1e9)
min_ = int(1e9)

def dfs(plus, minus, cross, div, sum, idx):
    global max_, min_
    if idx == n:
        max_ = max(max_, sum)
        min_ = min(min_, sum)
        return
    if plus:
        dfs(plus-1, minus, cross, div, sum+arr[idx], idx+1)
    if minus:
        dfs(plus, minus-1, div, sum-arr[idx], idx+1)
    if cross:
        dfs(plus, minus, cross-1, div, sum*arr[idx], idx+1)
    if div:
        dfs(plus, minus, cross, div-1, int(sum/arr[idx]), idx+1)

dfs(plus, minus, cross, div, arr[0],1)
print(max_)
print(min_)

 

면접 갔다와서 박살난 몸으로 자정 전에 챌린지를 위해 포스트를 쓰려고 했더니

자력으로 풀기엔 시간이 좀 촉박했다

 

다른 블로거 분의 풀이를 참고했다

 

 

근데 저 타겟넘버 프로그래머스 문제랑 굉장히 유사하다

 

배열의 첫 번째 숫자를 sum 초기값으로 두고, index를 1에서 시작하며 dfs의 깊이를 점점 늘려간다

 

그 다음 기호가 +,-,*,/인지에 따라 각 기호의 개수-1을 한 값을 dfs함수로 다시 넘겨준다

 

만약 depth가 n에 도달하면 현재 sum과 global에 저장된 max_,min_값 중에 max, min 값을 return하며 종료한다

 

bfs는 이제 좀 괜찮은데 dfs는 재귀함수라서 좀 생각하는 법을 길러야겠다