[백준] 14888번: 연산자 끼워넣기(실버 1, 파이썬)

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

14888번: 연산자 끼워넣기

 

 

아이디어

해당 문제는 dfs를 사용하여 풀었다. 

 

문제를 풀면서 나눗셈을 처리하기 위해 처음에는 //연산자를 사용했지만, 자꾸 답이 다르게 나오는 오류가 있었다.

print(int ( -1 / 3))    # 0
print(-1 // 3)          # -1

오류를 바로잡기 위해서는 위 두 연산의 차이를 알아야했다. 

파이썬의 -1 // 3 연산이 -1을 반환하는 이유는 floor division을 사용하기 때문이었다.

내부적으로 q=floor(a/n)로 동작하기 때문에 -0.XX의 경우 -1을 반환한다.

 

이해를 돕기 위해 참고하기 좋은 글을 가져왔다. 

https://stackoverflow.com/questions/19517868/integer-division-by-negative-number

Integer division by negative number

 

각 연산에 대한 처리를 구현하고 나서, 두 번째 문제를 마주쳤다.

바로 최댓값, 최솟값의 초기화였다.

처음에는 단순히 0으로 선언했지만, 이렇게되면 min(min_value, X) 일 때 X가 양수라면 무조건 0이 반환되기 때문에 문제가 생겼다.

그래서 본문을 다시 살펴보니 아래와 같은 부분이 있었다.

 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 

그래서 max를 -10억, min을 10억으로 초기화해주었다. (1e9는 실수이기 때문에 정수로 바꿔주었다.)

max_value = -int(1e9)
min_value = int(1e9)

 

 

전체 코드

N = int(input())
nums = [ int(x) for x in input().split() ]
add, sub, mul, div = map(int, input().split()) # 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수

max_value = -int(1e9)
min_value = int(1e9)

def dfs(curr, data):
    global add, sub, mul, div, max_value, min_value

    if curr == N:
        max_value = max(max_value, data)
        min_value = min(min_value, data)
        return
    
    if add > 0:
        add -= 1
        dfs(curr + 1, data + nums[curr])
        add += 1
    
    if sub > 0:
        sub -= 1
        dfs(curr + 1, data - nums[curr])
        sub += 1

    if mul > 0:
        mul -= 1
        dfs(curr + 1, data * nums[curr])
        mul += 1

    if div > 0:
        div -= 1
        dfs(curr + 1, int(data / nums[curr]))
        div += 1
    
dfs(1, nums[0])
print(max_value)
print(min_value)