문제
N개의 정수와 N - 1개의 연산자 정보가 주어졌을 때 중간에 연산자를 끼워넣어서 나온 결과의 최댓값과 최솟값 구하기
아이디어
모든 경우의 수는 결국 연산자가 나열되는 경우의 수이기 때문에 연산자 정보들에서 permutaions로 경우의 수를 구하고 중복을 제거한다음 구해보자
원소의 개수가 11이하이기 때문에 문제없이 완전탐색이 가능하다고 생각하였다.
나의 풀이
# N개의 정수와 N - 1개의 연산자가 주어졌을 때, 결과의 최대값과 최소값 구하기
from itertools import permutations
# 정수의 개수(n) 입력받기
n = int(input())
# n개의 정수 입력받기
data = list(map(int, input().split()))
# n - 1개의 연산자 정보 입력받기 +, -, x, / 개수
plus, minus, multiply, divide = map(int, input().split())
options = ['+'] * plus + ['-'] * minus + ['x'] * multiply + ['/'] * divide
unique_permutations = set(permutations(options))
option_list = list(unique_permutations)
# 연산자에 따라 계산해주는 함수
def calc(a, b, opt):
if opt == '+':
return a + b
elif opt == '-':
return a - b
elif opt == 'x':
return a * b
else:
result = abs(a) // abs(b)
# 양수, 음수 다르게 처리
# 음수인 경우, 몫만 구하고 -를 붙여서 리턴하기
if a < 0 or b < 0:
return -1 * result
else:
return result
# option_list를 이요하여 결과를 내보고 가장 큰값과 작은 값 구해보기
answer = []
for ol in option_list:
# 특정 경우의 연산자 리스트 보여줌.
result = data[0]
for i in range(1, len(data)):
result = calc(result, data[i], ol[i - 1])
answer.append(result)
print(max(answer))
print(min(answer))해설풀이
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 메서드 호출
dfs(1, data[0])
# 최댓값과 최솟값 차례대로 출력
print(max_value)
print(min_value)해설을 통해 알게된 점
처음에 이를 어떻게 재귀함수로 표현해야 할지 감이 잡히지 않았다.
연산자수를 빼고 재귀를 돌리고 다시 더하는 과정을 통해서 구할 수 있는 이유는
실행한 함수가 종료되어야 현재 함수가 실행되는 스택방식이기 때문이다.
