[BOJ] 14888. 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

 

1. 해결방법

"""
1. 아이디어
- 입력 받은 연산자를 리스트로 넣고 각 연산자의 수 만큼 재귀
- 재귀에서 n개를 선택 후 연산 결과가 크커나 작으면 변수 값 변경 한 다음 종료, print
- 백트래킹 for문을 돌면서 입력 숫자 원소와 연산자를 순차적으로 선책해서 모든 경우의 수를 연산

2. 시간복잡도
- O(N)

3. 자료구조
- 백트래킹 재귀
- 배열
"""

이 문제는 백트래킹을 이해하고 있지 않으면 접근하기 어려운 문제이다.

입력된 숫자의 순서를 바꾸지 않고, 입력을 받은 연산 기호 리스트를 이동해가면서 숫자 원소와 연자 처리를 한다.
연산을 처리하고 재귀를 사용해서 모든 경우를 계산하고 다시 돌아와서 연산 기호 리스트를 복구 하는 과정을 거친다. 물론 결고 값도 마찬가지..

 

 

2. 정답코드

입력 예제(1)

2
5 6
0 0 1 0

출력 예제(1)

30
30

 

입력 예제(2)

3
3 4 5
1 0 1 0

출력 예제(2)

35
17

 

입력 예제(3)

6
1 2 3 4 5 6
2 1 1 1

출력 예제(3)

54
-24

 

코드

import sys

# input
input = sys.stdin.readline

n = int(input())
number = list(map(int, input().split()))
op = list(map(int, input().split()))

start_num = number[0]

# 변수 초기화
max_v = -1e9
min_v = 1e9


# recur
def recur(num):
    global max_v, min_v, start_num

    # 종료지점
    if num == n:
        if start_num > max_v:
            max_v = start_num
        if start_num < min_v:
            min_v = start_num
        return


    # 재귀
    for i in range(4):
        result = start_num
        if op[i] > 0:
            if i == 0:
                start_num += number[num]
            elif i == 1:
                start_num -= number[num]
            elif i == 2:
                start_num *= number[num]
            else:
                if start_num > 0:
                    start_num //= number[num]
                else:
                    start_num = (-start_num // number[num]) * -1

            op[i] -= 1
            recur(num + 1)
            start_num = result
            op[i] += 1



# main
recur(1)
print(max_v)
print(min_v)