[백준 - python] 14888번: 연산자 끼워넣기

문제 링크

14888번: 연산자 끼워넣기 (acmicpc.net)

 

문제 풀이

n = int(input())
num_list = list(map(int, input().split()))
add_cnt, sub_cnt, mul_cnt, div_cnt = map(int, input().split())
max_ans, min_ans = -int(1e9), int(1e9)

def dfs(idx, add_cnt, sub_cnt, mul_cnt, div_cnt, result):
    global max_ans, min_ans

    if idx == n:
        max_ans = max(max_ans, result)
        min_ans = min(min_ans, result)
        return

    if add_cnt:
        dfs(idx + 1, add_cnt - 1, sub_cnt, mul_cnt, div_cnt, result + num_list[idx])
    if sub_cnt:
        dfs(idx + 1, add_cnt, sub_cnt - 1, mul_cnt, div_cnt, result - num_list[idx])
    if mul_cnt:
        dfs(idx + 1, add_cnt, sub_cnt, mul_cnt - 1, div_cnt, result * num_list[idx])
    if div_cnt:
        dfs(idx + 1, add_cnt, sub_cnt, mul_cnt, div_cnt - 1, int(result / num_list[idx]))

dfs(1, add_cnt, sub_cnt, mul_cnt, div_cnt, num_list[0])

print(max_ans)
print(min_ans)

14888 입출력 예시

 

*key point: 모든 연산자가 사용될 때까지(각 cnt -1) 결과를 저장(result)하고 모든 연산자가 사용됐을 때(idx == n) 최대, 최소값을 갱신한다. 재귀함수를 이용하여 자연스럽게 분기점을 구성하고, 최대, 최소값 갱신 이후 분기점으로 돌아오도록 구현한다.