백준 - 14888(연산자 끼워넣기, python)

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

14888번: 연산자 끼워넣기

문제 접근

• 주어진 사측연산 기호의 개수에 맞춰 주어진 수들로 만들 수 있는 최대값, 최소값을 구하는 문제
• dfs로 수를 하나씩 만들어서 가장 큰 값, 가장 작은 값을 출력

 

정답 코드

import sys

input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))

maximum = -1e9
minimum = 1e9

def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return
    # 각 기호가 있는 경우 
    if plus:
        dfs(depth +1, total + num[depth], plus -1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)
        
dfs(1, num[0], op[0], op[1], op[2], op[3])
print(maximum)
print(minimum)

처음에 너무 복잡하게생각해서 코드가 꼬였다...결국 다른사람 풀이를 참고했다.

코드부터 치는 습관 줄이고 근거를 토대로 단순 명료하게 구현하는 연습이 필요해보였다.

출저

https://velog.io/@kimdukbae/BOJ-14888-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0-Python

[BOJ 14888] 연산자 끼워넣기 (Python)