연산자 끼워 넣기

📌문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워 넣을 수 있는 N-1개의 연산자가 주어진다. 우리는 수와 수 사이에 연산자를 하나씩 넣어 수식을 하나로 만들 수 있는데 이때 주어진 수의 순서를 바꾸면 안된다.

식의 계산은 연산자 우선순위 무시하고 앞에서부터 진행한다. 나눗셈은 정수 나눗셈으로 몫만 취한다. 

N개의 수와 N-1개의 연산자가 주어졌을 때 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

📌풀이

모든 경우의 수를 계산하기 위해 DFS 혹은 BFS를 이용

사칙 연산을 중복으로 사용할 수 있기 때문에 중복 순열을 계산

만약 n=4라면 사칙연산 중 중복을 허용하여 3개를 뽑아 나열하는 모든 경우를 고려

 

📌코드

n = int(input())
# 연산을 수행하고자 하는 수 리스트
data = list(map(int, input().split()))
# 더하기 빼기 곱하기 나누기 연산자 개수
add, sub, mul, div = map(int, input().split())

# 최소, 최댓값 초기화
min_value = 1e9
max_value = -1e9


# DFS 메서드
def dfs(i, now):
    global min_value, max_value, add, sub, mul, div
    # 모든 연산자 다 사용한 경우, 최소, 최댓값 업데이트
    if i == n:
        min_value = min(min_value, now)
        max_value = max(max_value, now)

    else:
        # 각 연산자에 대해 재귀적으로 수행
        if add > 0:
            add -= 1
            dfs(i + 1, now + data[i])
            add += 1
        if sub > 0:
            sub -= 1
            dfs(i + 1, now - data[i])
            sub += 1
        if mul > 0:
            mul -= 1
            dfs(i + 1, now * data[i])
            mul += 1
        if div > 0:
            div -= 1
            dfs(i + 1, int(now / data[i]))
            div += 1


dfs(1, data[0])

print(max_value)
print(min_value)

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬