[백준 -실버1] 14888번 연산자 끼워넣기(완전탐색, 파이썬)

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

14888번: 연산자 끼워넣기

 

< 내 코드>

- 알고리즘 분류에 백트래킹, 브루트포스라고 되어있는데,,, 백트래킹 어제 하루종일 공부했는데 못하겠다.

- 그래서 완전탐색으로 구현함

- 틀렸던 부분 : 문제를 제대로 보지 않아서 숫자의 최대가 10인줄 알고 min_val, max_val을 정의할 때 10**11로했다.

                    --> 각 숫자의 최대, 최소는 100이기 때문에 100을 11번 곱했을때로 해야한다.

- 입력으로 연산자의 갯수가 차례대로 주어지는데 이것을 operations 리스트에 인덱스를 고려해서 옮겨줬다.

  -> 0: 덧셈, 1:뺄셈, 2:곱셈, 3:나눗셈

  -> 입력 : [2, 1, 1, 1] --> 변경 : [0,0,1,2,3]

- 그 후 permutations을 이용해서 가능한 모든 경우의 수를 뽑았고, 중복을 제거하기 위해 set을 사용했다.

- 모든 경우의수를 반복하면서 계산해준다. 이때 나눗셈에 주의할것(문제에 나온 조건대로 구현함)

from itertools import permutations
n = int(input())
nums = list(map(int, input().split()))
op = list(map(int, input().split()))
operations = [] #연산자를 담는 배열

#입력받은 연산자를 n-1 만큼 확장
#0:덧셈, 1:뺄셈, 2:곱셈, 3:나눗셈
for i in range(4):
    if op[i]>1:
        for j in range(op[i]):
            operations.append(i)
    else:
        if op[i]==0:
            continue
        else:
            operations.append(i)
        
operations = list(set(permutations(operations,n-1)))#연산자의 모든경우의 수 파악

min_val = 100**11 #나올 수 있는 최댓값으로 초기화
max_val = -100**11 #나올 수 있는 최솟값으로 초기화

for operation in operations:
    temp = nums[0]#첫번째 값으로 초기화
    for i in range(n-1):
        if operation[i]==0: #덧셈
            temp+=nums[i+1]
        elif operation[i]==1:#뺄셈
            temp-=nums[i+1]
        elif operation[i] ==2:#곱셈
            temp*=nums[i+1]
        elif operation[i]==3:#나눗셈
            if temp<0:#음수인 경우
                temp = -temp #음수로 바꿈
                temp = temp//nums[i+1]
                temp = -temp#다시 음수로 바꿔줌
            else:
                temp = temp//nums[i+1]
    min_val = min(min_val, temp)
    max_val = max(max_val, temp)
    
print(max_val)
print(min_val)