[BJ14888] 연산자 끼워넣기

🚩 문제 설명

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

14888번: 연산자 끼워넣기

⏱️ 시간 복잡도
▪ 순열의 값과도 같다.
▪ 나올 수 있는 연산자의 조합 과정이 시간복잡도가 된다.

◾ 숫자는 그대로, 쓸 수 있는 연산자만 갈아끼워 최댓값과 최솟값을 구하는 문제

◾ 세번째 줄에 들어오는 배열은 +, -, *, / 의 갯수를 뜻한다. 즉 2 0 1 0 이라고 들어오면 + 가 2개, *가 1개인 것을 뜻한다.

◾ 예시

[입력]
4
3 4 5 6
2 0 1 0

 

 

 

---

 

 

 

✅ 입출력

[입력]
1. n : 수의 개수
2. a(1) - a(n) : n개의 줄
3. 합이 n-1 인 4개의 정수 : +, -, *, / 각각의 개수
return
1. 최댓값
2. 최솟값

✔️ 예제 1

2
5 6
0 0 1 0

30
30

✔️ 예제 2

6
1 2 3 4 5 6
2 1 1 1

54
-24

✔️ 예제 3

4
3 4 5 6
2 0 1 0

72
23

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from copy import deepcopy

# sys.stdin = open('input2.txt', 'rt')
input = sys.stdin.readline

n = int(input())  # n 개의 수
a = list(map(int, input().split()))  # 주어지는 수열
b = list(map(int, input().split()))  # 연산자 배열


def dfs(idx):
    global ans, max_, min_

    # 숫자를 다 쓴 상태
    # 즉, n - 1 개의 연산이 된 상태
    if idx == n:
        max_ = max(max_, ans)
        min_ = min(min_, ans)
        return

    for i in range(4):
        ans_ = ans  # 이전의 연산이 되기 전의 값을 저장해둔다.
        if b[i]:  # 만약 연산자가 0이 아니라면
            if i == 0:  # +
                ans += a[idx]
            elif i == 1:  # -
                ans -= a[idx]
            elif i == 2:  # *
                ans *= a[idx]
            else:  # /
                # 양수를 나눌 때
                if ans >= 0:
                    ans //= a[idx]  # 그냥 나누기
                # 음수를 나눌 때
                else:  # 양수로 바꾸고 나서 나누고, 다시 음수로 변환
                    ans = (-ans // a[idx]) * -1

            b[i] -= 1  # 연산자를 하나 썻으니까 빼준다.
            dfs(idx + 1)  # 다음 수가 더해지러 간다.
            ans = ans_  # 연산되기 전으로 복구
            b[i] += 1  # 연산되기 전으로 복구


if __name__ == '__main__':
    ans = a[0]  # 첫번째 수 이후부터 연산이 시작된다.
    max_ = -2147000000  # 구할 수 있는 최댓값
    min_ = 2147000000  # 구할 수 있는 최솟값

    dfs(1)
    print(max_, min_)

💬 Point

➡️  dfs() 로 풀기

◾ 재귀, 백트랙킹을 이용하여 문제를 풀 수 있다.

 

sys.stdin = open('input2.txt', 'rt')
input = sys.stdin.readline

n = int(input())  # n 개의 수
a = list(map(int, input().split()))  # 주어지는 수열
b = list(map(int, input().split()))  # 연산자 배열

◾ 입력을 받는다.

 

if __name__ == '__main__':
    ans = a[0]  # 첫번째 수 이후부터 연산이 시작된다.
    max_ = -2147000000  # 구할 수 있는 최댓값
    min_ = 2147000000  # 구할 수 있는 최솟값

    dfs(1)
    print(max_, min_)

◾ 메인 함수는 다음과 같다.

예를 들어, 3 4 5 6 이 더해질 숫자라면 3부터 더해지므로 연산 결과가 나올 ans 에 3을 우선 초기화 해준다.

dfs() 는 그 다음 숫자부터 들어가야 한다. 즉, 4가 들어가야 하므로 4의 인덱스인 1이 들어가 dfs(1) 이 된다.

 

global ans, max_, min_

# 숫자를 다 쓴 상태
# 즉, n - 1 개의 연산이 된 상태
if idx == n:
    max_ = max(max_, ans)
    min_ = min(min_, ans)
    return

◾ 수를 계속 갱신할 수 있도록, ans 와 최대/최소를 전역변수 취해준다.

만약 dfs(idx) 로 들어온 값이 n 이라면 숫자들을 다 쓴 것이다. 즉 숫자 인덱스 0 1 2 3 을 다 쓰고 그 다음 4가 들어오게 된 것이다.

3 + 4 + 5 * 6 이러한 연산 과정이 끝난 것을 뜻하므로, max 인지 min 인지 따져주고 저장해준다.

 

for i in range(4):
    ans_ = ans  # 이전의 연산이 되기 전의 값을 저장해둔다.
    if b[i]:  # 만약 연산자가 0이 아니라면
        if i == 0:  # +
            ans += a[idx]
        elif i == 1:  # -
            ans -= a[idx]
        elif i == 2:  # *
            ans *= a[idx]
        else:  # /
            # 양수를 나눌 때
            if ans >= 0:
                ans //= a[idx]  # 그냥 나누기
            # 음수를 나눌 때
            else:  # 양수로 바꾸고 나서 나누고, 다시 음수로 변환
                ans = (-ans // a[idx]) * -1

◾ 백트랙킹 되어야 하므로 우선 이때까지 구핸 ans 값을 temp 값으로 저장을 해준다.

그리고 만약에 b[i] 가 0이 아니라면, 즉 연산자가 0 이 아니라면 연산자 대로 연산과정을 거친다.

해당 타겟의 숫자를 더해주거나, 빼주거나, 곱해주거나, 나눠준다.

근데 나눌 때 양수라면 그냥 나눠도 되지만, 음수라면 양수로 바꾸고 나서 나누고 다시 음수로 변환을 해야한다.

 

b[i] -= 1  # 연산자를 하나 썻으니까 빼준다.
dfs(idx + 1)  # 다음 수가 더해지러 간다.
ans = ans_  # 연산되기 전으로 복구
b[i] += 1  # 연산되기 전으로 복구

◾ 백트랙킹 되는 부분이다.

연산자를 하나 썻으니 카운팅에서 하나 빼준다. 그리고나서 다음 순서의 수가 더해질 수 있도록 dfs(idx + 1) 을 해준다.

만약 return 되어 돌아온다면 연산되기 전으로 복구를 시켜줘야하므로 일시적으로 저장해놓았던 ans 를 복구해준다.

연산자 카운팅도 다시 복구를 해줘야한다.

 

 

 

 

 

 

 

 

 

 

 

 

# 알고리즘 백준 연산자 끼워넣기 python dfs

# 알고리즘 연산자끼워넣기 파이썬 bj14888 python dfs

---