[BOJ / 파이썬] 14888: 연산자 끼워넣기

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

단계 : 백트래킹

알고리즘 분류 : 브루트포스 알고리즘, 백트래킹 

 

풀이:

숫자의 개수, 숫자, 각 연산기호의 개수가 순서대로 입력으로 들어온다. 실제 연산과는 다르게 연산기호의 순서는 무시하고 앞에서부터 연산하면 된다.

 

문제에서 요구한 순서대로 연산기호를 리스트에 넣어둔다. solve 함수에서는 어떤 연산기호를 꺼내서 사용할 것인지 정해서 가능한 모든 값을 찾는 것이 목표이다.

 

solve함수 내부에서는 각 연산기호를 기준으로 하여 경우의 수를 구하기 위해 4까지의(연산기호 개수가 4) 범위를 for문으로 돌며 해당 연산기호가 사용 가능한지(값이 0 초과인지) 본 후 사용 가능하다면 해당 연산기호를 사용하여 연산을 진행한다. 이때 사용한 연산기호는 남은 개수에서 1을 빼주고(opnum[i] -= 1) 재귀를 돌려준다. 그렇게 실행된 재귀는 방금 고른 연산기호를 하나 사용한 opnum(남은 연산기호들의 개수)과 방금 연산된 값을 가지고 진행된다. temp가 현재까지 연산된 식의 값이다.

 

재귀 solve가 끝나고 나왔을 때 다음 for문으로 이루어지게 하기 위해 시작할 때 bef에 저장해둔 temp의 값을 다시 temp에 넣어준다. 같은 이유로 재귀가 끝났을 경우 for문으로 진행되는 다음 경우는 현재 연산기호를 사용하지 않았을 때이므로 다시 opnum의 값을 +1 해준다.

 

연산을 진행하는 과정에서 eval 함수를 사용했다. eval 함수는 문자열로 이루어진 식을 넣어주면 그 식의 값을 반환해주는 함수이다. 예를 들어 "1+3-2"를 eval함수에 인자로 넣어주면 1+3-2의 값인 2가 반환된다. 우리는 지금 연산기호를 리스트 op에 넣어서 관리하고 있고 i로 해당 연산기호의 인덱스에 접근할 수 있는만큼 eval함수를 적극 활용했다.

 

음수를 나누는 방법은 C++ 14의 기준을 따른다고 하여 검색해서 진행했다. 파이썬과 연산이 다르기 때문에 i == 3일 때 즉 현재 사용하고 있는 연산 기호가 //이고 현재 값(temp)가 음수일 때만 따로 if문으로 구현하였다.

 

이런식으로 진행할 경우 모든 연산기호의 조합을 찾을 수 있어 해당 숫자들과 주어진 연산기호로 가능한 모든 값들을 찾을 수 있다. n이 count와 같다면 모든 연산기호를 사용하여 값을 구해낸 것이므로  res 리스트에 추가해준다. solve 함수가 종료되면 res 리스트에는 가능한 모든 경우의 수를 마친 값들이 들어있으므로 max와 min함수를 이용하여 최댓값과 최솟값을 출력해준다.

 

"삼성 SW 역량 테스트 기출 문제 1"이라고 한다. 화이팅!

 

코드

import sys


def solve(n, count):
    global temp, res
    if n == count:
        res.append(temp)
    else:
        for i in range(4):
            if opnum[i] > 0: // 해당 연산기호가 사용 가능한 개수가 남아있는지
                bef = temp // 현재 temp 저장(solve에서 나왔을 때 다음 for문을 위해)
                if i == 3 and temp < 0:
                    temp = -int(eval(str(-temp) + op[i] + str(num[n + 1])))
                else:
                    temp = int(eval(str(temp) + op[i] + str(num[n + 1])))
                opnum[i] -= 1
                solve(n + 1, count)
                temp = bef //다음 for문을 사용하기 위해 방금 있던 경우의 수 이전으로 돌려주기
                opnum[i] += 1 //위와 동일


op = ["+", "-", "*", "//"]
t = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
opnum = list(map(int, sys.stdin.readline().split()))
res = []
temp = num[0]
solve(0, t - 1)
print(max(res))
print(min(res))