[Baekjoon 14888 / python / 실버1] 연산자 끼워넣기

import sys

input = sys.stdin.readline

n = int(input())

numList = list(map(int, input().split()))

add, sub, mul, div = map(int, input().split())

maxValue = -1e9

minValue = 1e9

def DFS(i, calc):

    global add, sub, mul, div, maxValue, minValue

    if i == n:  # 수열의 끝에 오면 최대/최솟값 구하기, 수열번호와 인덱스번호 헷갈리지 말자.

                # 수열번호가 1이면 인덱스번호는 0

        maxValue = max(maxValue, calc)

        minValue = min(minValue, calc)

    else:

        if add > 0:

            add -= 1

            DFS(i+1, calc + numList[i])  # 덧셈연산을 한 경우의 수 구하러 가기

            add += 1  # 구하고 왔으면 다른연산을 한 경우의 수도 구하러 가야 하니 다시 돌려놓기

        if sub > 0:

            sub -= 1

            DFS(i+1, calc - numList[i])

            sub += 1

        if mul > 0:

            mul -= 1

            DFS(i+1, calc * numList[i])

            mul += 1

        if div > 0:

            div -= 1

            DFS(i+1, int(calc / numList[i]))  # calc // numList[i] 를 하면, "내림" 해 버려서 음수일 경우 문제가 생긴다

            div += 1

DFS(1, numList[0])  # 수열의 첫번째 번호, 첫번째 숫자 인자로 넣고 DFS 실행

print(int(maxValue))

print(int(minValue))

 

DFS로 해결할 수 있는 문제이다.

 

최소/최대값을 구하는 연산자의 순서에 뭔가 규칙이 있을 거라 생각해서 이리저리 생각하다가, 결국 DFS로 해결한 문제이다.  DFS로 최대/최소값을 업데이트하면서 모든 경우의 수를 다 구하면 크게 머리쓰지 않고 해결할 수 있다.

 

난 maxValue를 왜 -1e9로 하는지 이해가 안됐었다. 1e9도 아니고 왜 작은 값으로 하는지 몰랐었는데, maxValue값을 업데이트할 때 어떤 값이 오든 첫 값은 maxValue가 되는데 애매한 값이 maxValue에 초기화되어 있으면 여기서 문제가 생길 수 있기 때문이었다. 문제에서 제시된 수의 최대/최소값이 10억~-10억이기 때문에 -1e9, 1e9로 초기화하는 것이다.

물론 반드시 이 값으로 초기화 해야하는 것은 아니다. 약간 관례적인 이유도 있다.

 

단 두가지 신경쓸 점이 있는데, 나누기 연산을 할 때 꼭 int(calc / numList[i]) 이렇게 해야 한다.

calc // numList[i]를 하면 생기는 문제가, // 연산은 "내림"을 하기 때문에 음수일 경우 값에 오차가 생긴다.

예를 들어 -7 나누기 2 일 경우

int(-7 / 2)  -> -3

-7 // 2       -> -4

이렇게 값이 차이난다. 결국 -3.5에서 처리를 어떻게 하느냐의 차이인데, int는 -3.5에서 뒤를 아예 떼고 -3을 만들지만 // 연산은 -3.5에서 더 낮은 값으로 "내림"하여 -4를 만들어 버린다.

 

또 마지막에 출력할 때 int를 붙여주지 않으면 틀렸습니다 라고 뜬다. 이유는 모른다. 테스트 케이스는 전부 통과했지만 제출하면 문제가 생겨서 꼭 int를 붙여줘야 한다.