백준 알고리즘 14888: 연산자 끼워 넣기(Python)

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

14888번: 연산자 끼워넣기

---

문제 해결을 위한 과정

이 문제의 경우 부호에 해당하는 리스트를 따로 만든 후 해당 리스트에서 보호의 순사가 바뀜에 따라 값도 바뀌게 되므로 순서가 중요한 순열로 뽑아야 합니다. 따라서 숫자의 경우 num이라는 리스트를 만들어 넣어주고 부호의 경우 따로 x라는 리스트를 만든 후 permutations를 통해 숫자보다 하나 적게 뽑은 후 ( 3 + 3처럼 부호의 경우 숫자보다 하나 적어야 함) 교차하여 부호와 숫자가 모두 포함이 된 리스트를 만든 후 이를 계산하는 calc함수를 구현하면 쉽게 해결할 수 있습니다.

---

문제 해결을 위한 팁

저의 경우 isdigit()를 통해서 부호와 숫자를 합쳐진 리스트에서 구별했는데 이때 int형애는 isdigit()을 사용할 수 없기 때문에 str을 이용하여 우선 다 문자 형태로 바꿔준 후에 isdigit()을 이용하였습니다.

소스코드

 

from itertools import permutations
 
def calc(arr):
  prev = int(arr[0])
  for i in range(1, len(arr)-1):
    if arr[i].isdigit() == False:
      if arr[i] == '+':
        prev += int(arr[i+1])
      elif arr[i] == '-':
        prev -= int(arr[i+1])
      elif arr[i] == '//':
        if prev >= 0:
          prev = prev // int(arr[i+1])
        else:
          prev *= -1
          prev = prev // int(arr[i+1])
          prev *= -1
      elif arr[i] == '*':
        prev *= int(arr[i+1])
  return prev
 
N = int(input())
num = list(map(int, input().split()))
numOfA, numOfB, numOfC, numOfD = map(int, input().split())
 
x = []
while True:
  if numOfA > 0:
    x.append('+')
    numOfA -= 1
  if numOfB > 0:
    x.append('-')
    numOfB -= 1
  if numOfC > 0:
    x.append('*')
    numOfC -= 1
  if numOfD > 0:
    x.append('//')
    numOfD -= 1
  if numOfA == 0 and numOfB == 0 and numOfC == 0 and numOfD == 0:
    break
 
maximum = int(1e9)*-1
minimum = int(1e9)
 
for xx in list(permutations(x, N-1)):
  j = 0
  arr = []
  for i in range(N-1):
    arr.append(str(num[i]))
    arr.append(str(xx[j]))
    j += 1
  arr.append(str(num[-1]))
  result = calc(arr)
  maximum = max(maximum, result)
  minimum = min(minimum, result)
 
print(maximum)
print(minimum)