[백준 14888] 연산자 끼워넣기 - python (solved.ac - 실버 1)

14888번: 연산자 끼워넣기

풀이

문제를 보았을 때 알 수 있는 힌트

순열을 통해 문제를 풀면 되지 않을까 생각이 들었다. 조건에서도 개수가 많지 않아서 충분히 브루트포스로 풀 수 있을 것으로 보였다.

연산자들을 하나의 리스트에 모두 뽑고 순열 함수를 뽑아서 숫자 사이에 넣어 계산을 하였다.

또한 최대와 최소의 초기값을 10억,-10억으로 두고 문제를 풀었더니 쉽게 풀렸다.

 

import sys
from itertools import permutations

input = sys.stdin.readline

n= int(input())
a=list(map(int,input().split()))
operator=list(map(int,input().split()))
operator_4=[]
for _ in range(operator[0]):
    operator_4.append(0)
for _ in range(operator[1]):
    operator_4.append(1)
for _ in range(operator[2]):
    operator_4.append(2)
for _ in range(operator[3]):
    operator_4.append(3)
operators_perm=list(set(permutations(operator_4,n-1)))

result_min=1000000001
result_max=-1000000001
for operator_perm in operators_perm:
    temp=a[0]
    for i in range(n-1):
        if operator_perm[i]==0:
            temp+=a[i+1]
        if operator_perm[i]==1:
            temp-=a[i+1]
        if operator_perm[i]==2:
            temp*=a[i+1]
        if operator_perm[i]==3:
            if temp<0:
                temp=-temp
                temp//=a[i+1]
                temp=-temp
            else:
                temp//=a[i+1]
    result_min=min(result_min,temp)
    result_max=max(result_max,temp)
print(result_max)
print(result_min)​

 

다만 이렇게 푸는 것보다 다른 사람들의 푼 방식을 참고해봤는데 재귀함수를 통해서 문제를 푸는 것을 볼 수 있었다. 굳이 순열을 쓰지 않고도 효율적으로 푼 것으로 보아 참고하기 위해 아래 코드를 추천한다.

 

n = int(input())
numbers = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

# print(n)
# print(numbers)
# print(add, sub, mul, div)

results = []

def dfs(i, now, add, sub, mul, div):
    global results
    
    if i == n:
        results.append(now)
    
    if add > 0:
        dfs(i+1, now+numbers[i], add-1, sub, mul, div)

    if sub > 0:
        dfs(i+1, now-numbers[i], add, sub-1, mul, div)

    if mul > 0:
        dfs(i+1, now*numbers[i], add, sub, mul-1, div)

    if div > 0:
        if now<0:
            dfs(i+1, -(-now // numbers[i]), add, sub, mul, div-1)
        else:
            dfs(i+1, now//numbers[i], add, sub, mul, div-1)
dfs(1, numbers[0], add, sub, mul, div)
# print(results)
print(max(results))
print(min(results))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon14888.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리