[백준알고리즘] 14888번: 연산자 끼워넣기 -Python

[백준알고리즘] 14888번: 연산자 끼워넣기 -Python

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

14888번: 연산자 끼워넣기

백트래킹 문제이다.

왜지? 그냥 DFS 문제이다.

 

단계별 풀기에는 분명 백트래킹으로 되어있는데 페이지 밑에 알고리즘 분류에는 또 브포로 나와있다..

 

주절주절했듯이 그냥 모든 경우를 찾아야한다. 가지치기(pruning)할 경우를 나눈다고 해봤는데 minimum과 maximum을 둘 다 구해야 하는 문제이기 때문에 마땅히 나오지 않았다. 그래서 그냥 굴려봤더니 됐다.

 

괜히 머리썼나 싶을 정도였지만 다른 사람들의 코드를 통해서 배운 점이 위안거리이다. 

"음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. "라는 조건을 만족하기 위해서 처음에는 위의 식처럼 그대로 했었다. 다음은 아래의 내 코드처럼 바꿨다. 만족하고 다른 사람들의 코드를 봤는데 되게 간단해서 놀랬다.

 

밑에 코드처럼 길게 쓸 필요없이 int(now/numList[level])을 인자로 바로 넘겨주면 되는 것이다. 이유는 파이썬에서 음수의 나눗셈과 관련이 있다. 파이썬에서 몫을 구하는 연산자인 //를 사용하게 되면 -3 // 2 == -2 가 된다. 몫만 구하기 때문에 항상 내림을 하기 때문이다. 그렇다면 일반 나눗셈 연산자 /를 사용하게 되면 -3 / 2 == -1.5 가 된다. 따라서 -1.5에 int를 씌우는 것과 같기 때문에 -1이 출력되는 것이다. 이 결과는 문제가 원하는 결과이기 때문에 코드가 줄게 된다.

 

아래는 코드

import sys

sys.setrecursionlimit(10**9)

N = int(sys.stdin.readline())
numList = list(map(int, sys.stdin.readline().split()))
operator = list(map(int, sys.stdin.readline().split()))

minimum = 10**9
maximum = -10**9

def dfs(now, level):
    if level == N:
        global minimum, maximum
        maximum = max(now, maximum)
        minimum = min(now, minimum)
        return

    if operator[0] > 0:
        operator[0] -= 1
        dfs(now + numList[level], level+1)
        operator[0] += 1

    if operator[1] > 0:
        operator[1] -= 1
        dfs(now - numList[level], level+1)
        operator[1] += 1

    if operator[2] > 0:
        operator[2] -= 1
        dfs(now * numList[level], level+1)
        operator[2] += 1

    if operator[3] > 0:
        result = abs(now) // numList[level]
        if now < 0:
            result *= -1

        operator[3] -= 1
        dfs(result, level+1)
        operator[3] += 1


now = numList[0]
dfs(now, 1)

sys.stdout.write(str(maximum) + "\n" + str(minimum) + "\n")

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다