알고리즘/이것이 코딩테스트다

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