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

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

요구사항

1. 시간 제한, 메모리 제한 문제를 풀기에 충분하다.
2. 나눗셈의 경우 몫만 출력할 것. 
   1. 음수를 양수로 나눌 경우, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼다.
3. N개의 수로 이루어진 수열 사이에 연산자를 적절히 끼워 최대 최소값을 구해라. 

설계

1. 백트래킹을 사용, 모든 경우의 수를 비교하여 출력한다.

구현

import sys
input = sys.stdin.readline

def main():
    N = int(input())  # 숫자의 개수
    lst = list(map(int, input().split()))  # 숫자 리스트
    operators = list(map(int, input().split()))  # 연산자 리스트

    def dfs(n, temp):
        if n == N-1:  # 종료 조건
            return temp, temp

        results = []
        if operators[0] > 0:  # 덧셈
            operators[0] -= 1
            mx, mn = dfs(n+1, temp + lst[n+1])
            results.append((mx, mn))
            operators[0] += 1
        
        if operators[1] > 0:  # 뺄셈
            operators[1] -= 1
            mx, mn = dfs(n+1, temp - lst[n+1])
            results.append((mx, mn))
            operators[1] += 1
        
        if operators[2] > 0:  # 곱셈
            operators[2] -= 1
            mx, mn = dfs(n+1, temp * lst[n+1])
            results.append((mx, mn))
            operators[2] += 1
        
        if operators[3] > 0:  # 나눗셈
            operators[3] -= 1
            mx, mn = dfs(n+1, int(temp / lst[n+1]))  # 나눗셈은 정수 나눗셈
            results.append((mx, mn))
            operators[3] += 1

        # 모든 결과를 비교해서 최댓값과 최솟값 반환
        max_result = max(r[0] for r in results)
        min_result = min(r[1] for r in results)
        return max_result, min_result

    mx, mn = dfs(0, lst[0])  # 첫 번째 숫자로 시작
    print(mx)
    print(mn)

if __name__ == "__main__":
    main()

• max_result = max(r[0] for r in results)
• results에 저장된 최댓값들만 모아 그것들의 최댓값을 max_result 에 저장함.