[CT] 연산자 배치하기

1. 문제

• n개의 정수 순서대로 (순서 바꿀 수 없음)
• n-1개의 연산자 배치

  • 덧셈, 뺄셈, 곱셈

  • 연산자 간 우선 순위 무시, 앞에서부터 차례대로 연산

    ⇒ 가능한 식의 최솟값, 최댓값?

2. 풀이

• 1차 시도: 백트래킹을 시도해 봄…
  • 조삼모사를 백트래킹으로 했던 것처럼 순열을 구하는 함수 구조를 이용해서 dfs/백트래킹과 연산값을 구하는 함수를 이용해서 풀어보려고 함
  • 입력받은 연산자의 개수를 기반으로 연산자 배열을 만들고, 해당 배열의 인덱스에 대해 순열을 만들어서 해결해보려고 하였으나 연산자 순서의 중복을 고려하지 않아서 연산횟수도 쓸데없이 많아지고 점점 산으로 가버림..!
• 정답 코드 해설:
  • dfs를 이용한 백트래킹을 할 때 depth와 연산자 개수에 대한 변수를 함께 이용
    • depth는 입력으로 받은 정수 배열의 인덱스와 동일함
    • 연산자 조합을 만들 때 개수를 1개씩 차감하고 depth를 1개씩 더해가며, 바로 연산을 하면서 최솟값과 최댓값을 구함!

3. 코드

def dfs(depth, total, plus, sub, multi):
    global MIN, MAX
    if depth == n:
        MIN = min(MIN, total)
        MAX = max(MAX, total)
    
    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, sub, multi)

    if sub:
        dfs(depth + 1, total - num[depth], plus, sub - 1, multi)
    
    if multi:
        dfs(depth + 1, total * num[depth], plus, sub, multi - 1)

n = int(input())

num = list(map(int, input().split()))
plus, sub, multi = map(int, input().split())

MIN, MAX = float("INF"), -float("INF")
dfs(1, num[0], plus, sub, multi)
print(MIN, MAX)

+α

정답 코드가 아주 예술적이고 예쁘다… :)

언젠가 저런 코드를 내 손으로 작성할 수 있기를,,,ㅠ_ㅠ

• 참고 : https://velog.io/@jimeaning/%EC%BD%94%EB%93%9C%ED%8A%B8%EB%A6%AC-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%B0%B0%EC%B9%98%ED%95%98%EA%B8%B0