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

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

공부 날짜 : 2022.09.01
정답 참조 여부:△

숫자가 연속적으로 주어지고 연산자의 개수가 주어질때 최대값과 최솟값을 구하는 문제로 처음에 떠오른 방법은 모든 순열을 구해서 최대최소를 구하는 방법과 단순히 dfs로 문제를 푸는 방법이 떠올랐다.

n의 최대가 11이기 때문에 순열을 구하더라도 별로 오래걸리지 않을거 같았지만 순열을 구하는 방법이 바로 떠오르지 않아서 그냥 dfs로 풀었다.

차후 순열을 구해서 하는방법도 도전할 예정이다.

소스코드는 별로 어렵지 않았다. 초반에는 UnboundLocalError이 발생해서 애매하게 잡혀있던 지역변수 전역변수에 대한 감을 잡을 수 있었고

가장 어려웠던(?) 이해가 안됬던 부분은 나눗셈 부분이었다.

#나눗셈
elif i == 3 and data[3] > 0:
data[i] -= 1
dfs(num // A[index], index+1)
data[i] += 1

로 코드를 작성했는데 계속 '틀렸습니다'가 나왔다. 도저히 어떤 부분이 틀렸는지 못찾고 정답을 찾아 봤는데 dfs로 구현한 코드는 대부분 내가 작성한 것과 비슷하게 코드를 짜서 크게 참조가 되지 못했다.

정답은

#나눗셈
elif i == 3 and data[3] > 0:
data[i] -= 1
dfs(int(num / A[index]), index+1)
data[i] += 1

로 a//b 와 int(a/b)에 차이가 있음을 코랩에서 디버깅 해보면서 찾을 수 있었다.
a//b의 경우 -1//3에서 -1이 나오고 int(-1/3)은 0이 나온다.

이런 차이를 확실하게 파악할 수 있었고 코딩테스트가아닌 공부과정에서 찾은 것에 감사한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())

#계산해야하는 수의 리스트
A = list(map(int, input().split()))

#연산식의 개수가 들어있는 리스트
data = list(map(int,input().split()))

#최대와 최소를 저장하는 변수
min_result = int(10e9)
max_result = int(-(10e9))


def dfs(num,index):
    global data, min_result, max_result
    
    if index == n:
        min_result = min(min_result,num)
        max_result = max(max_result,num)
        return
    
    for i in range(4):
        #덧셈
        if i == 0 and data[0] > 0:
            data[i] -= 1
            dfs(num + A[index], index+1)
            data[i] += 1
        
        #뺄셈
        elif i == 1 and data[1] > 0:
            data[i] -= 1
            dfs(num - A[index], index+1)
            data[i] += 1
            
        #곱셈
        elif i == 2 and data[2] > 0:
            data[i] -= 1
            dfs(num * A[index], index+1)
            data[i] += 1
            
        #나눗셈
        elif i == 3 and data[3] > 0:
            data[i] -= 1
            dfs(int(num / A[index]), index+1)
            data[i] += 1
            
            

dfs(A[0], 1)

print(max_result)
print(min_result)