[WEEK01/DAY05] 백준 문제 : 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

문제 설명 :

100 이하의 자연수로 이루어진 수열 A[n](2 ≤ n ≤ 11) 이 주어진다.

그리고 그 수열 사이에 들어갈 연산자들이 주어진다.

주어진 수열과 연산자들을 가지고 만들어낼 수 있는 최댓값과 최솟값을 구하는 문제이다.

 

주어진 조건들이 몇개 더 있는데, 궁금하다면 위 링크에 들어가서 확인할 수 있다.

 

 

 

풀이 :

1. 가능한 연산자의 배열 방법을 모두 나열한 순열을 구한다.

2. 중복되는 데이터를 삭제하기 위해 set() 자료형을 사용한다.

      (ex. 더하기 연산자가 2개 있으면 ' + + '에서 서로 위치만 바꾼 ' + + '가 한번 더 나올 수 있으므로)

3. 모든 경우의 수에 대해 일일히 계산하면서... 최댓값과 최솟값을 찾는다.

 

나는 가능한 순열을 모두 구하고, 그걸 또 중복 제거하고, for문을 두 번 사용하여 풀었는데

다른 답안을 보니 재귀호출을 사용하는 더 깔끔한 풀이 방법이 있었다. (시간도 더 짧다)

탐색 관련 알고리즘을 더 공부해 보아야겠다.

 

 

아래는 나의 답안이다. 좋은 답안은 아니라고 생각한다.

import sys
from itertools import permutations

n = int(sys.stdin.readline().strip())
numbers = [0] * n
numbers = list(map(int, sys.stdin.readline().split()))
operators = [0] * 4
operators = list(map(int, sys.stdin.readline().split()))

# 연산자들을 1차원 리스트에 나열한다
oprList = [0] * (n-1)
k = 0
for i in range(4):
    for j in range(operators[i]):
        oprList[k] = i
        k += 1

# 연산자의 가능한 순열(중복값 제거)
permus = list(permutations(oprList, n-1))
cases = list(set(permus))

# 계산해보고 최솟값 최댓값 찾기
minimum = 1000001000
maximum = -1000001000
for case in cases:
    calc = numbers[0]
    for i in range(n-1):
        if case[i] == 0:
            calc = calc + numbers[i+1]
        elif case[i] == 1:
            calc = calc - numbers[i+1]
        elif case[i] == 2:
            calc = calc * numbers[i+1]
        elif case[i] == 3:
            if calc < 0:
                calc = -( abs(calc) // numbers[i+1] )
            else:
                calc = calc // numbers[i+1]
    
    if calc < minimum:
        minimum = calc
    if calc > maximum:
        maximum = calc

print(f'{maximum}\n{minimum}')