[백준] 14888. 연산자 끼워넣기

문제

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

 

코드

n = int(input())
num = list(map(int, input().split()))
operation = list(map(int, input().split()))  # +, -, *, /

maxi = -1e9
mini = 1e9


def dfs(idx, result, plus, minus, multiply, divide):
    global maxi, mini

    if idx == n:
        maxi = max(result, maxi)
        mini = min(result, mini)
        return

    if plus > 0:
        dfs(idx + 1, result + num[idx], plus - 1, minus, multiply, divide)
    if minus > 0:
        dfs(idx + 1, result - num[idx], plus, minus - 1, multiply, divide)
    if multiply > 0:
        dfs(idx + 1, result * num[idx], plus, minus, multiply - 1, divide)
    if divide > 0:
        dfs(idx + 1, int(result / num[idx]), plus, minus, multiply, divide - 1)


dfs(1, num[0], operation[0], operation[1], operation[2], operation[3])

print(maxi)
print(mini)

 

풀이

n = int(input())
num = list(map(int, input().split()))
operation = list(map(int, input().split()))  # +, -, *, /

maxi = -1e9
mini = 1e9

n은 주어질 숫자의 개수다.

num은 n개의 숫자들이 담겨져 있는 배열이다.

operation은 더하기, 빼기, 곱하기, 나누기 순으로 각각 몇개가 있는지 담겨있는 배열이다.

 

maxi는 만들 수 있는 식 결과의 최대값이다. 후에 dfs 과정에 최대값을 비교하며 찾을것이기 때문에 처음부터 아주 작은 수로 초기화 해놓는다.

mini는 만들 수 있는 식 결과의 최소값이다. 마찬가지로 후에 dfs 과정에 최소값을 비교하며 찾을것이기 때문에 처음부터 아주 큰 수로 초기화 해놓는다.

 

def dfs(idx, result, plus, minus, multiply, divide):
    global maxi, mini

    if idx == n:
        maxi = max(result, maxi)
        mini = min(result, mini)
        return

dfs 함수이다. 매개변수 idx는 dfs의 깊이를 의미한다.

매개변수 result는 현재까지 만들어진 식의 계산 결과값이다.

매개변수 plus, minus, multiply divide는 각 더하기, 빼기, 곱하기, 나누기 연산자 별로 몇번이나 더 사용할 수 있는지에 대한 횟수다.

 

만약 idx(깊이)가 n(숫자의 개수)와 같아진다면 

현재 최대값, 최소값을 각각 result(식의 계산 결과값)와 비교한 후 최대값, 최소값을 갱신하고 return 한다.

 

if plus > 0:
    dfs(idx + 1, result + num[idx], plus - 1, minus, multiply, divide)
if minus > 0:
    dfs(idx + 1, result - num[idx], plus, minus - 1, multiply, divide)
if multiply > 0:
    dfs(idx + 1, result * num[idx], plus, minus, multiply - 1, divide)
if divide > 0:
    dfs(idx + 1, int(result / num[idx]), plus, minus, multiply, divide - 1)

idx가 n에 도달할때 까지는 이 코드를 dfs 방법으로 수행한다.

 

각각의 연산자들에 대해서 쓸 수 있는 횟수가 0 초과라면

dfs를 재귀호출 해주는데 각 매개변수에 대해서

깊이를 1 더하고, 수행하고 있는 연산자에 맞는 연산을 result에 처리해주고, 수행하고 있는 연산자의 사용 가능 횟수를 -1 해준다.

 

dfs(1, num[0], operation[0], operation[1], operation[2], operation[3])

print(maxi)
print(mini)

dfs를 실행하는데 함수의 매개변수는 깊이는 1, result는 받은 숫자들의 맨 처음 숫자, operation에 받은 각 연산자들의 사용 가능 횟수를 매개변수로 넣어준다.

 

dfs를 실행하고 난 뒤의 최대값, 최소값을 출력한다.