이코테_BFS, DFS) Q19 연산자 끼워 넣기

책 349쪽

풀지 못했으니까 바로 정답 소스

*정답 소스

num = int(input())
data = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

min_value = 1e9
max_value = -1e9

def dfs(i, now):       # 위치, 현재 값
    global min_value, max_value, add, sub, mul, div

    if i == num:    # 모든 연산자를 사용했을 때
        min_value = min(min_value, now)
        max_value = max(max_value, now)
    else:
        if add > 0:
            add -= 1	# + 수 차감
            dfs(i+1, now + data[i])		# 연산자를 모두 사용했을 때 나옴
            add += 1	# + 복구, 위에서 나온 뒤 sub로 내려감
        if sub > 0:
            sub -= 1
            dfs(i+1, now - data[i])
            sub += 1
        if mul > 0:
            mul -= 1
            dfs(i+1, now * data[i])
            mul += 1
        if div > 0:
            div -= 1
            dfs(i+1, int(now/data[i]))
            div += 1
dfs(1, data[0])

print(max_value)
print(min_value)

-아직 문제를 많이 풀어본 건 아니지만 dfs, bfs를 어떻게 적용해야 할지 감이 잘 안 온다

 

내 접근:

1. 연산자도 list형으로 받아서 bfs를 사용하면서 큐에 순서를 섞어서 넣어야겠다. -> 순서 섞으려면 반복문 오지게 돌렸겠지

1-2. 연산자 수를 입력받으니까, 연산자로 바꿔서 넣어줘야겠네 

1-2-1. 이차원 리스트 등장..ㅎ

2. ..? 이러면 연산자 list... bfs를..???

-> 이렇게 사고가 산으로 열심히 가고 있었다.

 

정답 소스의 접근:

연산자에 대해 재귀(dfs)를 이용해서 완전 탐색 수행 (아주 단순,,)

 

피드백:

재귀에 대한 개념도 추가적으로 볼 필요가 있음

 

+디버거 너무 좋다