백준 14888 연산자 끼워넣기 삼성 SW역량테스트 (Python, 완전탐색, 순열)

백준 14888 연산자 끼워넣기 바로가기

문제 해석

N개의 수로 이뤄진 수열 A의 사이사이에 주어지는 연산자로 넣어 최대값과 최솟값을 구하는 문제이다.

문제 접근

문제를 보고 완전탐색으로 풀어야 한다는 것을 알 수 있다.
수의 개수가 최대 11개이기 때문에 충분하다.
그렇다면 연산자를 모든 경우의 수로 sort해야되는데 이걸 어떻게 할까?
나는 이 때 순열이 생각났다.
연산자를 각각의 개수만큼 리스트에 넣고 이를 순열함수를 통해 모든 경우의 수로 나타내는 것이다.
그렇게만 한다면 그 후에 최대, 최소값을 구하는 것은 쉽다.

이렇게 생각하고 문제 풀이를 시작했다.

문제 풀이

import sys
import itertools
N = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().split()))
cal_count = list(map(int, sys.stdin.readline().split()))
cal = ['+','-','*','//']
cal_besort = []
for i in range(4):
    for j in range(cal_count[i]):
        cal_besort.append(cal[i])

우선 연산자의 각각의 개수만큼 cal_besort리스트에 넣어준다.

for i in itertools.permutations(cal_besort,len(cal_besort)):
	result = A[0]
    A_index = 1
    for k in i:
        if k=='+':
            result += A[A_index]
            A_index+=1
        elif k=='-':
            result -= A[A_index]
            A_index+=1
        elif k=='*':
            result *= A[A_index]
            A_index+=1
        else:
            if result<0: #음수를 양수로 나누는 경우
                result = (-result)//A[A_index]
                result = -result
                A_index+=1
            else: #양수를 양수로 나누는 경우
                result = result//A[A_index]
                A_index+=1

이렇게 넣어준 cal_besort로 itertools의 permutations를 사용해서 순열로 만들어주고 반복문을 돌린다.
result에 A[0]를 넣어주고 순열로 돌렸을 때의 리스트에 연산자를 확인하면서 result에 계산한다.
이때 연산자가 //일 경우에는 문제에서 조건을 주었기 때문에 상황을 나누어서 계산해준다.

if min_result>result:
        min_result = result # 최소값
    if max_result<result:
        max_result = result # 최대값

후에 result와 최소 최대를 비교하여 값을 저장한다.

제출 코드

import sys
import itertools
N = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().split()))
cal_count = list(map(int, sys.stdin.readline().split()))
cal = ['+','-','*','//']
cal_besort = []
for i in range(4):
    for j in range(cal_count[i]):
        cal_besort.append(cal[i])
min_result = float('inf')
max_result = float("-inf")
for i in itertools.permutations(cal_besort,len(cal_besort)):
    result = A[0]
    A_index = 1
    for k in i:
        if k=='+':
            result += A[A_index]
            A_index+=1
        elif k=='-':
            result -= A[A_index]
            A_index+=1
        elif k=='*':
            result *= A[A_index]
            A_index+=1
        else:
            if result<0: #음수를 양수로 나누는 경우
                result = (-result)//A[A_index]
                result = -result
                A_index+=1
            else: #양수를 양수로 나누는 경우
                result = result//A[A_index]
                A_index+=1
    if min_result>result:
        min_result = result # 최소값
    if max_result<result:
        max_result = result # 최대값

#출력
print(max_result)
print(min_result)