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

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

14888번: 연산자 끼워넣기

 

import sys

n = int(input()) 
num = list(map(int, input().split())) # 수열 입력 
op = list(map(int, input().split())) # 연산자 입력 

max_min = [ -sys.maxsize + 1, sys.maxsize ] # 최댓값 최솟값 리스트 

def dfs(depth, total, plus, minus, multi, divide):
    if depth == n: # 모든 연산을 다 하면 
        max_min[0] = max(total, max_min[0]) # 최댓값을 비교하여 저장 
        max_min[1] = min(total, max_min[1]) # 최솟값을 비교하여 저장 
        return
    
    # elif 가 아닌 이유는 모든 경우를 다 돌리기 위해서 
    if plus:
        dfs(depth+1, total+num[depth], plus-1, minus, multi, divide)
    if minus:
        dfs(depth+1, total-num[depth], plus, minus-1, multi, divide)
    if multi:
        dfs(depth+1, total*num[depth], plus, minus, multi-1, divide)
    if divide:
        # 풀이조건 중 "양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것" 때문에 // 안 
        dfs(depth+1, int(total/num[depth]), plus, minus, multi, divide-1)
    
dfs(1, num[0], op[0], op[1], op[2], op[3])

print(max_min[0])
print(max_min[1])

 

처음엔 순열로 풀면 되겠다! 싶었고 구현을,, 어떻게 해야할지 몰라서 구글링 해보니 순열로 풀면 시간초과 난다더라. 호락호락하지 않아..(PyPy 로 풀면 풀림) 

 

일단 DFS를 돌면서 최대최소 저장을 위해 max_min 변수를 뒀다. 파이썬에서는 그냥 정수로 선언하고 다른 스코프에서 변경하려고 하면 immutable 이라서 새로 메모리할당을 해버리고 기존거는 버려버려서 global 로 해줘야 하지만 난 그냥 list 로 선언해버리는게 더 편해서.. 저렇게 변수 선언을 해주었다. 

 

구글링하면서 여러 포스팅을 찾아보니 1e9 이렇게 최대최솟값을 적어두신 분들이 많던데 파이썬에서 공식적인 정수형 최대 최소값은 sys.maxsize, -sys.maxsize + 1 이다. 

 

그다음에 DFS 인수를 보면 depth는 dfs 깊이를 저장하기 위해서 있고 1부터 시작한다. total은 매 depth를 돌면서 계산한 값을 저장했다. 그 이후로는 plus, minus, multi, divide는 남은 사칙연산 횟수를 입력받았다. 사칙연산들은 따로 list 로 넣어도 될 것 같긴 한데 가독성을 위해서 그냥 풀어 썼다. 

 

dfs 내부로는 depth가 (1부터 시작해서) n까지 돌면 종료조건으로 현재까지의 total을 가지고 최댓값, 최솟값 비교로 저장하고 리턴한다. 그리고 아직 뎁스가 n이 아니면 사칙연산들을 수행하게 되는데, elif 가 아닌 if 문을 4개 둔 이유는 순서가 중요하다보니 각각의 경우에 다 dfs를 돌려봐야 하기 때문에 +-*/ 로 시작하는 경우를 다 돌리기 위해서다. 

 

또 나눗셈 연산에서 // 가 아니라 int(~~~) 인데 이는 문제 조건에서 "음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다." 라는 조건 때문이다. 

 

-4 // 3 을 하면 -2 가 되지만, -4/3 을 하면 -1.33333... 이 되고, 여기에 int(-4/3) 을 하면 소수 부분을 버려서 -1 이 된다. 

 

일단 나누는 두 수의 부호가 다르면 +로 바꿔서 몫을 구한 뒤 -를 붙여주고, a = bq + r 에 의해 나머지 r이 계산된다. 

 

 

 

 

참고자료

https://velog.io/@kimdukbae/BOJ-14888-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0-Python

[BOJ 14888] 연산자 끼워넣기 (Python)

https://hashcode.co.kr/questions/1092/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%80-%EC%A0%95%EC%88%98-%EC%B5%9C%EC%86%8C%EA%B0%92-%EC%B5%9C%EB%8C%80%EA%B0%92-%EC%A0%9C%ED%95%9C%EC%9D%B4-%EC%97%86%EB%82%98%EC%9A%94

파이썬은 정수 최소값 최대값 제한이 없나요?

https://jeonggyun.tistory.com/228

C++ 음수의 나눗셈 / 나머지