[백준] No.14888_연산자 끼워넣기 01

 

14888번: 연산자 끼워넣기

 문제 해석) 숫자와 연산자의 개수가 주어진다. 주어진 개수만큼의 연산자 위치를 바꿔가면서 가장 큰 결과와 가장 작은 결과를 순서대로 출력한다. 라는 문제이다. (단, 사칙연산 순서를 따르지 않고 앞에서부터 계산한다.) 자세한 입력 범위와 조건들은 위의 백준 사이트를 참고하면 된다. 알기 쉽게 예를 들어보자면, 이런 거다.

 

4 8 3 5        # 입력할 숫자의 개수 N (2 ≤ N ≤ 11)
4 8 3 5        # 무작위 숫자 N개 (1 ≤ 숫자 ≤ 100)
1 1 1 0        # 연산자(+ - × ÷의 개수)

가능한 경우의 수
1) 4 + 8 - 3 × 5                2) 4 + 8 × 3 - 5                3) 4 - 8 + 3 × 5
4) 4 - 8 × 3 + 5                5) 4 × 8 + 3 - 5                6) 4 × 8 - 3 + 5

 

 우선 제일 먼저 생각한 것은 연산자의 개수이다. 개수를 입력해서 그 수만큼 연산을 실행해야 하는데...

나는 for문을 사용해서 새로운 리스트에 연산자들을 전부 넣은 뒤 브루트 포스를 활용하여 하나씩 연산을 실행하려 했다.

저런 식으로 연산자를 하나하나 전부 넣고 계산을 해서 최댓값과 최솟값을 출력하는 문제면 백트래킹보다는 브루트 포스에 더 가깝지 않나? 라는 생각이 든다.

 

N = int(input())
numList = list(map(int, input().split()))
opCntList = list(map(int, input().split()))
opList = []

for _ in range(opCntList[0]):
    opList.append('+')
for _ in range(opCntList[1]):
    opList.append('-')
for _ in range(opCntList[2]):
    opList.append('*')
for _ in range(opCntList[3]):
    opList.append('/')
    
print(opList)

 그런데 이런... 생각해보니 append를 사용해버리면 리스트에 +가 아니라 '+'로 들어가버린다. 연산자로써의 기능을 상실하고 문자열로 리스트에 추가된다는 거다. 따로 작업을 하는 것이 아니라 바로 연산을 해야 한다. 그래서 함수의 매개 변수로 값을 받아와야 겠다고 생각했다.

 

N = int(input())
num = list(map(int, input().split()))
opCnt = list(map(int, input().split()))

maxNum = minNum = 0

def doDFS(depth, plus, minus, multiply, divide, result):
    if opCnt[0] != 0:
        doDFS(depth + 1, opCnt[0] - 1, opCnt[1], opCnt[2], opCnt[3], result + num[depth])
        
    if opCnt[1] != 0:
        doDFS(depth + 1, opCnt[0], opCnt[1] - 1, opCnt[2], opCnt[3], result - num[depth])
        
    if opCnt[2] != 0:
        doDFS(depth + 1, opCnt[0], opCnt[1], opCnt[2] - 1, opCnt[3], result * num[depth])
        
    if opCnt[3] != 0:
        doDFS(depth + 1, opCnt[0], opCnt[1], opCnt[2], opCnt[3] - 1, result / num[depth])
        
doDFS(1, opCnt[0], opCnt[1], opCnt[2], opCnt[3], num[0])
print(maxNum)
print(minNum)

 numLIst와 opCntList를 각각 num과 opCnt로 바꾸었다. 너무 길어지기도 하고 List인 것은 어차피 알 수 있는 사실이니까.

IndexError가 떴다. 코드를 다시 읽어보니 doDFS 함수 내에 if문을 보면 doDFS 매개변수를 plus, minus 같은 걸로 받아서 연산을 해야 한다.

그러지 않고 opCnt로 받으니 오류가 생긴 것 같다. 너무 무지성 코드 복붙을 했던 느낌이 있었는데 역시나...

 

N = int(input())
num = list(map(int, input().split()))
opCnt = list(map(int, input().split()))

maxNum = -1e9
minNum = 1e9


def doDFS(depth, plus, minus, multiply, divide, result):
    global maxNum, minNum
    
    if depth == N:
        maxNum = max(result, maxNum)
        minNum = min(result, minNum)
        
        return
    
    if opCnt[0] != 0:
        doDFS(depth + 1, plus - 1, minus, multiply, divide, result + num[depth])
        
    if opCnt[1] != 0:
        doDFS(depth + 1, plus, minus - 1, multiply, divide, result - num[depth])
        
    if opCnt[2] != 0:
        doDFS(depth + 1, plus, minus, multiply - 1, divide, result * num[depth])
        
    if opCnt[3] != 0:
        doDFS(depth + 1, plus, minus, multiply, divide - 1, result // num[depth])
        
doDFS(1, opCnt[0], opCnt[1], opCnt[2], opCnt[3], num[0])

print(maxNum)
print(minNum)

 ...조금 많이 고쳤다. 우선 위에서 언급한 부분을 고치고 나니까 또다시 IndexError가 떴다. 결과를 반환하지 않아서 생긴 오류같다.

그러니까 연산자를 전부 사용하여 식을 완성했을 때(depth가 가장 높을 때), 값을 반환하고 다시 다른 연산을 해야 하는데

그 반환 부분의 코드가 없어서 오류가 생겼다. depth가 최고여도 끝나지 않고 리스트 값을 벗어나니까.

 

 그리고 반환 부분을 짜다가 생각난 건데, 최댓값과 최솟값을 0으로 초기화 해주면 안 됐었다.

만약에 최댓값이 0보다 작다면? 최솟값이 0보다 크다면? 연산 오류가 생긴다. 그래서 동시에 코드를 수정해줬다.

못해도 -10억보다는 크다고 하니, 어떤 최댓값이든 -10억보다는 크다는 거다. 그래서 maxNum을 -1e9로 초기화했다.

마찬가지로 10억보다는 작다고 하니, 어떤 최솟값이든 10억보다는 작다는 거다. 그래서 minNum을 1e9로 초기화했다.

 

 마지막으로 문제 조건을 읽었다. "나눗셈은 정수 나눗셈으로 몫만 취한다." 예 문제 좀 잘 읽읍시다. / 연산이 아니라 // 연산이다.

 

 하지만 어림도 없지 틀렸다. 음...뭐가 문제인지 한참을 고민하다가 미심쩍은 부분을 확인해봤다.

마지막으로 수정한 나눗셈 부분이다. 아래가 연산에 관한 본문을 그대로 옮긴 것이다.

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.

 

 이게 계속 걸려서 실험을 해봤더니 신기한 결과가 나왔다.

분명 내가 알고 있는 // 연산자는 나눗셈 연산에서 나머지를 버리고 몫만 취하는 것이고,

int 형 변환은 소수점 밑은 버리고 오로지 정수 부분만 취하는 거라고 배웠다.

-4를 3으로 나누면 -1.333333...이다. 이것의 몫은 -1이고. 

그런데 // 연산자를 계산한 결과를 보면 나머지를 버리는 게 아니라 가우스 연산을 하는데...?

음수 연산에서는 무언가 바뀌는 듯하다... 교수님께 여쭤보고 다시 와야할 듯하다.