[DFS/BFS] 연산자 끼워 넣기 (BAEKJOON 14888번)

1. 문제

숫자가 N만큼 주어지고 연산자가 N-1개 만큼 주어졌을 대 최대값, 최소값을 출력하라.

연산자 순서는 + - * / 순이다.

나눌땐 몫만 취할 것 (음수를 나눌 경우 양수로 나눈 뒤 - 붙임)

 

2. 입력

# SET - 1
2
5 6
0 0 1 0

# SET - 2
3
3 4 5
1 0 1 0

# SET - 3
6
1 2 3 4 5 6
2 1 1 1

 

3. 출력

# SET - 1
30
30

# SET - 2
35
17

# SET -3
54
-24

 

4. 풀이

예전에 풀때는 완전탐색으로 permutation을 사용해 풀었지만,

 

조금 공부하고나니 DFS로 푸는 방법이 보였다.

마치 친구와 당구를 하면서, 맨날 당구비를 내다보니 길이보이는 느낌이랄까..

 

근데 중요한건 아직 시야가 편협하다는 것

max값을 구할 때는 -가 max일 경우를 생각해서 -INF부터 검사했어야 됐는데,

0으로 해놨다.

이것 찾느라 한참 걸렸다는...

근데 웃긴건 min 값은 INF부터 검사함

 

여튼, 나동빛의 풀이를 보고 DFS하는 방법에 대해 조금은 이해를 해서

연산자를 하나씩 사용하면서 남은 연산자가 0일 때 값을 갱신하는 방법을 썼다.

 

 

아참, 그리고 완전탐색을 사용했을 땐,

메모리 528580kb, 시간 1432ms

DFS방법을 사용했을 땐,

28776kb, 시간 132ms 

메모리는 약 1/20만큼, 시간은 약 1/10만큼 줄어든 것을 확인할 수 있었다.

 

5. 코드

N = int(input())
numbers = list(map(int, input().split()))
cals = list(map(int, input().split()))

INF = int(1e9)
max_answer = -INF
min_answer = INF

CALCULATOR = ['+','-','*', '/']

def calcul(a, b, e):
    if e == '+':
        return a+b
    elif e == '-':
        return a-b
    elif e == '*':
        return a*b
    else:
        return int(a/b)

def dfs(this_idx, numbers, temp_cal, temp_answer):
    global max_answer
    global min_answer
    if sum(temp_cal) == 0:
        max_answer = max(max_answer, temp_answer)
        min_answer = min(min_answer, temp_answer)
    else:
        for i, c in enumerate(temp_cal):
            if c != 0:
                temp_cal[i] -= 1
                temp = calcul(temp_answer, numbers[this_idx], CALCULATOR[i])
                dfs(this_idx+1, numbers, temp_cal, temp)
                temp_cal[i] += 1

dfs(1, numbers, cals, numbers[0])

print(max_answer)
print(min_answer)