백준 - 14888 연산자 끼워넣기 (파이썬)

문제 링크 : https://www.acmicpc.net/problem/14888
난이도 : 실버 1

문제풀이

---

문제 정리

• 순서대로 연산을 했을 때 가장 큰 값과 가장 작은 값을 구한다.

분석

• 해당 문제는 같은 것이 있는 순열 문제이다.

• 순열처럼 구하는데 같은 것(중복)이 있는 것은 카운팅을 해줘야한다.

  • 순열처럼 구한다는 것
    해당 페이지에 파이썬으로 순열을 구하는 방법을 볼 수 있다.
    순열에서는 현재 뽑은 수를 체크한 사실을 다음 함수 호출 시 같이 넘기고, 함수가 끝난 후 초기화 한다.

  for i in range(len(arr)):
        if not check[i]:
            check[i] = True
            perm(arr, n-1, temp+[arr[i]])
            check[i] = False
    return result

• 위와 같은 방식을 모든 연산 에서 카운팅 해주며 적용해준다.

  if opers[0] > 0:
          opers[0] -= 1
          oper(opers, arr[1:], temp + arr[0], n-1)
          opers[0] += 1
      if opers[1] > 0:
          opers[1] -= 1
          oper(opers, arr[1:], temp - arr[0], n-1)
          opers[1] += 1
      if opers[2] > 0:
          opers[2] -= 1
          oper(opers, arr[1:], temp * arr[0], n-1)
          opers[2] += 1
      if opers[3] > 0:
          opers[3] -= 1
          oper(opers, arr[1:], int(temp / arr[0]), n-1)
          opers[3] += 1

시간복잡도

• 수는 최대 100개이고 연산자는 최대 99개이다
• $\left\lvert \frac{99!}{a!b!c!d!} \right\rvert$
  a+b+c+d = 99

전체코드

---

N = int(input())
nums = list(map(int, input().split()))
opers1 = list(map(int, input().split()))

max_val, min_val = -1e9, 1e9

def oper(opers, arr, temp, n):
    global max_val, min_val
    if n == 0:
        max_val = max(max_val, temp) 
        min_val = min(min_val, temp)
        return

    if opers[0] > 0:
        opers[0] -= 1
        oper(opers, arr[1:], temp + arr[0], n-1)
        opers[0] += 1
    if opers[1] > 0:
        opers[1] -= 1
        oper(opers, arr[1:], temp - arr[0], n-1)
        opers[1] += 1
    if opers[2] > 0:
        opers[2] -= 1
        oper(opers, arr[1:], temp * arr[0], n-1)
        opers[2] += 1
    if opers[3] > 0:
        opers[3] -= 1
        oper(opers, arr[1:], int(temp / arr[0]), n-1)
        opers[3] += 1

oper(opers1, nums[1:], nums[0], N-1)
print(max_val)
print(min_val)

정리 및 느낀점

---

• 재귀시 방문기록을 남길 때 파라미터로는 업데이트된 방문기록을 보내주고
• 초기화 한다음 다음 줄로 넘어가야한다
• 1 // 3 은 1이 나옴...