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

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

이 문제는 연산자문제.

처음에 저는 헤맸던 게

공학용 계산기를 많이 뚜둘기다보니

연산자 우선순위까지

전부 다 고려하는 줄 알았습니다.

그렇게 되면 난이도가 미친듯이 상승하기 때문에

여기서는 우선순위없이

먼저 받는 순서대로 숫자를 계산해주었습니다.

이거는 간단한 DFS문제였습니다.

숫자를 순서대로 봐가면서

모든 식의 케이스를 살펴봅니다.

그 뒤에, 최대 최소를 구하는 식으로

모든 케이스를 구하는 문제였습니다.

저는 길찾기 문제를 풀 때

주로 BFS를 사용하다보니

이 문제를 풀 때에도

본능적으로 BFS를 먼저 선택했습니다.

그랬더니 결과가 뭔가 이상했습니다.

저의 코드를 봐보니

저런 식으로

하나가 띄어지는 경우가 생기더군요.

그러니깐, 1 2 3 4 5 6

이 순서대로 더해야하는데

이게 종종 잘못돌아서

1 3 4 6 이렇게 더해지는 케이스가 생기더군요.

 

# 백준 14888번

N = int(input())

nums = list(map(int, input().split()))
cal = list(map(int, input().split()))
nums_visited = [[False] for _ in range(N)]
nums_visited[0] = True

mi = 1e9
ma = -1e9
# 최대 최솟값에 대한 초기값.
# 최소는 가장 큰 수로
# 최대는 가장 작은 수로 최소화.
# 저렇게 안하고, 처음에 9999999999,0 이런 식으로 했더니 틀렸다고 뜨네요
# 구글링해본 결과, 저러콤 해줘야 문제에서 요구한 10억을 만족하는 듯 합니
cal_sum = 0

for i in range(4):
    cal_sum += cal[i]


def making(cal_do, now):
    global cal_sum
    global mi
    global ma
    if cal_do == N:
        mi = min(mi, now)
        ma = max(ma, now)
        # print(mi)
        # print(ma)
        # print("finish")
        return
    for j in range(4):
        if not nums_visited[cal_do] == True and cal[j] > 0:
            cal[j] -= 1
            tmp = now
            print(tmp)
            print(nums[cal_do])
            if j == 0:  # 더하기
                now += nums[cal_do]
                # print("plus")
            if j == 1:  # 빼기
                now -= nums[cal_do]
                # print("minus")
            if j == 2:  # 곱하기
                now *= nums[cal_do]
                # print("dobule")
            if j == 3:  # 나누기
                now = int(now / nums[cal_do])
                # print("divide")
            nums_visited[cal_do] = True
            # print("now_cal")
            # print(now)
            making(cal_do + 1, now)

            # 백트레킹도 해줍니다.
            cal[j] += 1
            nums_visited[cal_do] = False
            now = tmp


making(1, nums[0])
print(ma)
print(mi)

이 문제는 DFS라는 건 쉽게 생각이 나도

백트레킹에 대해서 잘 모른다면

헤메기 쉬운 문제였습니다.

저도 이전에 백트레킹 문제를 처음 접했을 때는

이게 뭐지...싶으면서

상당히 문제가 난해하게면 느껴졌는데

백트레킹 기법을 알고나니

난해한 부분이 많이 해소가 되었습니다.

이건 간단한 백트레킹이라

이런 류의 백트레킹을 기억해두신다면

길찾기 문제에 큰 도움이 되실 겁니다.