[알고리즘/순열, 백트래킹] 14888번 : 연산자 끼워넣기 - python

링크 : https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

---

• 문제
• 소요시간: 26분 40초

---

• 설계하기(접근방법) 

1. 입력받기

순열과

연산자 개수를 입력받는다

 

2. 구현하기

백트래킹으로 풀어야 더 빠르게 풀 수 있는 문제지만

시간초과가 널널해서 다행히 시간초과는 나지 않았다

 

방법은

순열을 이용해서 연산자 경우의 수 리스트를 만든 후

각 케이스를 방문하면서 결과를 list에 append해준다

 

그 후 max와 min을 출력한다

 

3. 출력하기

 

 

---

• 코드(출력)

from itertools import permutations

n = int(input())
num_list= list(map(int,input().split()))
plus, minus, multi, divide = map(int,input().split())
operator = ['+' for _ in range(plus)] + ['-' for _ in range(minus)] + ['*' for _ in range(multi)] + ['/' for _ in range(divide)]
per = list(set(permutations(operator, n-1)))

result = []

for i in per:
    start = num_list[0]
    for j in range(0, n - 1):
        if i[j] == '+':
            start += num_list[j + 1]
        if i[j] == '-':
            start -= num_list[j + 1]
        if i[j] == '*':
            start *= num_list[j + 1]
        if i[j] == '/':
            if start < 0:
                start = -start
                start //= num_list[j + 1]
                start = -start
            else:
                start //= num_list[j + 1]
    result.append(start)



print(max(result))
print(min(result))

---

• 얻어갈 부분

1. 백트래킹으로 풀었으면 더 좋았겠지만 일단 순열에 대해서 배웠다