알고리즘/이것이 코딩테스트다
19_연산자 끼워넣기
happenundo
2024. 2. 6. 18:24
728x90
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱
www.acmicpc.net
itertools 패키지의 permutations 클래스를 활용해서 풀었다.
단, permutations를 사용해서 나올 수 있는 연산자 리스트의 후보를 구할 때,
한 연산자가 2개 이상 들어 있을 경우, 같은 연산자 리스트가 연산자 리스트 후보에 들어 있을 수 있으므로
set으로 바꿔줘서 중복을 없애주는 방식으로 구현했다.
내 풀이 코드
# 14888번: 연산자 끼워넣기
from itertools import permutations
INF = 1e10
n = int(input()) # 숫자 개수
arr = list(map(int, input().split())) # 숫자
plus, minus, multiply, divide = map(int, input().split())
oper = []
for _ in range(plus):
oper.append("+")
for _ in range(minus):
oper.append("-")
for _ in range(multiply):
oper.append("*")
for _ in range(divide):
oper.append("/")
# 숫자 리스트와 연산자 리스트가 주어졌을 때, 값을 계산해서 리턴해주는 함수
def calculate(arr, oper):
result = arr[0]
for i in range(n-1):
op = oper[i]
num = arr[i+1]
if op == "+":
result += num
elif op == "-":
result -= num
elif op == "*":
result *= num
elif op == "/":
if result < 0:
temp = abs(result) // num
result = -temp
else:
result //= num
return result
candidates = list(set(list(permutations(oper, n-1))))
max_result = -INF
min_result = INF
for cand in candidates:
temp_result = calculate(arr, cand)
max_result = max(max_result, temp_result)
min_result = min(min_result, temp_result)
print(max_result)
print(min_result)
이 문제는 완전 탐색 혹은 DFS 혹은 BFS로 풀 수 있는 문제다.
나는 itertools의 permutations 클래스를 사용해서 풀었으니 DFS를 활용한 다른 풀이 코드에 대해 다시 공부하도록 하겠다.
풀이 코드
import sys
sys.setrecursionlimit(10**6)
n = int(input())
# 연산을 수행하고자 하는 수 리스트
data = list(map(int, input().split()))
# 더하기, 빼기, 곱하기, 나누기 연산자 개수
add, sub, mul, div = map(int, input().split())
# 최댓값과 최솟값 초기화
min_value = 1e10
max_value = -1e10
# 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)
위 코드 dfs 함수에서
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
이 테크닉을 잘 기억해두자.
add -= 1
을 한 후, 재귀함수로 들어간 후, 재귀함수에서 빠져나온 경우 다시 add += 1을 해준다.
728x90