백준 삼성 코딩 기출 문제 - 연산자 끼워넣기 python

백준 삼성 코딩 기출 문제 - 연산자 끼워넣기 python

출처 : BAEKJOON ONLINE JUDGE

연산자 끼워넣기 (https://www.acmicpc.net/problem/14888)

문제 설명

N개의 수로 이루어진 수열에서 각 수마다 N-1개의 연산자가 주어집니다. 각 연산자는 사칙연산으로 덧셈(+), 뺄셈(-), 곱셈(x), 나눗셈(%)가 주어집니다. 수의 순서를 바꾸지 않으면서 각 연산을 적용해보고, 식의 결과의 최대값과 최소값을 구하는 문제입니다.

문제 풀이

재귀 함수를 이용해 구현하면 문제 풀이는 쉽습니다.

[1] 입력을 받습니다.

덧셈, 뺄셈, 곱셈, 나눗셈 순서로 operation에 저장합니다.

n = int(input()) number = list(map(int, input().split())) operation = list(map(int, input().split())) # +, -, X, %

[2] 최대 최소가 될 max_, min_에 초기화합니다.

max_, min_ = -1e9, 1e9

[3] 연산자를 적용하는 재귀 함수 구조로 구현합니다.

def solve(counter, answer, add, sub, mul, div):     global max_, min_     if counter== n: # operation 수와 일치하다면 종료         max_ = max(max_, answer) # 최대         min_ = min(min_, answer) # 최소         return     if add: # 덧셈         solve(counter+1, answer+number[counter], add-1, sub, mul, div)     if sub: # 뺄셈         solve(counter+1, answer-number[counter], add, sub-1, mul, div)     if mul: # 곱셈         solve(counter+1, answer*number[counter], add, sub, mul-1, div)     if div: # 나눗셈, 음수의 경우 원하는 사칙연산 값이 안나오므로 양수로 처리 계산 결과 음수 처리         solve(counter+1, answer//number[counter] if answer > 0 else -((-answer)//number[counter]),               add, sub, mul, div-1)

전체 코드

n = int(input()) number = list(map(int, input().split())) operation = list(map(int, input().split())) # +, -, X, % max_, min_ = -1e9, 1e9 def solve(counter, answer, add, sub, mul, div):     global max_, min_     if counter== n: # operation 수와 일치하다면 종료         max_ = max(max_, answer) # 최대         min_ = min(min_, answer) # 최소         return     if add: # 덧셈         solve(counter+1, answer+number[counter], add-1, sub, mul, div)     if sub: # 뺄셈         solve(counter+1, answer-number[counter], add, sub-1, mul, div)     if mul: # 곱셈         solve(counter+1, answer*number[counter], add, sub, mul-1, div)     if div: # 나눗셈, 음수의 경우 원하는 사칙연산 값이 안나오므로 양수로 처리 계산 결과 음수 처리         solve(counter+1, answer//number[counter] if answer > 0 else -((-answer)//number[counter]),               add, sub, mul, div-1)         solve(1, number[0], operation[0], operation[1], operation[2], operation[3]) print('%d\n%d'%(max_, min_))