[백준/Python(파이썬)] 14888

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

연산자 끼워넣기(삼성 SW 역량 테스트 기출 문제 1) - 실버 1

💫 알고리즘

백트래킹

후보 해를 한 단계씩 구축하며, 조건에 맞지 않는 경우 이전 단계로 되돌아가 다른 선택지를 탐색

깊이 우선 탐색(DFS)과 유사하며, 유망하지 않은 경로를 조기에 배제하여 탐색 효율을 높임

퍼즐, 조합 최적화, N-Queen 문제 등 복잡한 문제에서 가능한 해의 공간을 체계적으로 탐색

---

💡 풀이방향

🐢 백트래킹을 사용하여 연산자들을 모든 가능한 순서로 조합하여 최댓값과 최솟값을 찾는 문제

1️⃣ 수(A)의 순서는 변경할 수 없음

2️⃣ 연산자 우선순위를 무시하고 왼쪽에서 오른쪽으로 차례대로 연산

3️⃣ 나눗셈은 C++14 기준: 음수를 양수로 나눈 후 몫을 취하고, 그 몫을 다시 음수로 변환

4️⃣ 연산자의 모든 경우의 수 탐색을 위해 백트래킹(DFS) 사용

5️⃣ 모든 가능한 연산 순서를 탐색

: 각 연산자의 경우를 따로 탐색해야 하므로 여러 개의 if문을 둔 후 재귀적 탐색

6️⃣ 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어짐

---

🌟 코드 구현 + 👀 풀이

[전체 코드]

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
op = list(map(int, input().split()))

max_val = -1e9
min_val = 1e9

def dfs(index, result, add, sub, mul, div):
    global max_val, min_val

    if index == N:
        max_val = max(max_val, result)
        min_val = min(min_val, result)
        return

    if add:
        dfs(index + 1, result + A[index], add - 1, sub, mul, div)
    if sub:    
        dfs(index + 1, result - A[index], add, sub - 1, mul, div)
    if mul:
        dfs(index + 1, result * A[index], add, sub, mul - 1, div)
    if div:
        dfs(index + 1, int(result / A[index]), add, sub, mul, div - 1)

dfs(1, A[0], op[0], op[1], op[2], op[3])

print(int(max_val))
print(int(min_val))

 

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

op에는 연산자 개수 리스트 저장([+, -, *, /] 개수)

 

max_val = -1e9

min_val = 1e9

조건에 따라; 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력값

최댓값, 최솟값 초기화

 

백트래킹(DFS): def dfs(index, result, add, sub, mul, div):

if index == N:
    max_val = max(max_val, result)
    min_val = min(min_val, result)
    return

모든 숫자를 사용한 경우(index == N) 최댓값과 최솟값을 갱신 후 종료

max_val과 min_val을 최종적으로 가장 큰 값, 작은 값으로 갱신

 

# dfs함수 내 여러 개의 if문
    if add:
        dfs(index + 1, result + A[index], add - 1, sub, mul, div)
    if sub:    
        dfs(index + 1, result - A[index], add, sub - 1, mul, div)
    if mul:
        dfs(index + 1, result * A[index], add, sub, mul - 1, div)
    if div:
        dfs(index + 1, int(result / A[index]), add, sub, mul, div - 1)

🤔 왜 if-elif가 아니라 여러 개의 if문을 쓰나요?

🐢 예시를 들어 설명해 볼게요!

 위의 입력값에서 나올 수 있는 경우는

1️⃣ 3 + 4 = 7, 7 * 5 = 35

2️⃣ 3 * 4 = 12, 12 + 5 = 17

두 가지 경우입니다.

 dfs 첫 호출에서 A1과 A2에 대한 모든 가능한 연산을 확인하려면 if-elif가 아니라 개별적으로 if문을 써야 모든 경우를 탐색할 수 있어요. 첫 호출에서 각 연산자별로 루트가 분기되고, 각 루트에서 또 분기되며 index가 N과 같아졌을 때 값을 max_val, min_val과 비교하며 최댓값, 최솟값을 갱신하는 식이죠! 또 중요한 점은 연산자를 사용했으면 -1을 해줘야 한다는 점인데요, -1을 안 해주면 사용할 연산자가 없는데도 재귀가 실행될 수 있기 때문이에요.

 

🤔 if div: 에서 왜 result // A[index]가 아니라 int(result / A[index])을 하나요?

🐢 음수를 양수로 나눌 때는 C++14의 기준을 따른다는 문제의 조건 때문이에요.

파이썬의 경우 // 을 할 경우 결괏값이 항상 작은 정수 방향으로 내림 처리되는데요.

print(-5 // 2)을 하면 -2가 아닌 -3이 출력돼요. C++14는 -5 // 2의 경우 -2기 때문에

이에 맞춰 int(result / A[index])로 소수점을 버려버리는 거예요!

 

dfs(1, A[0], op[0], op[1], op[2], op[3])

초기 값 설정: A[0]에서 시작 / 연산자 개수를 dfs에 전달 

 

print(int(max_val))

print(int(min_val))

🤔 이건 int함수를 왜 쓰나요? 그대로 max_val, min_val을 출력하면 되는 거 아닌가요?

🐢 처음에 max_val = -1e9, min_val = 1e9로 초기화했었죠? 만약 이 값이 갱신이 안 되면 1e9, -1e9 모두 실수이기 때문에 1000000000.0과 같이 소수점이 포함된 형태로 출력돼요. 이를 피하기 위해 int 함수를 사용해 정수 형태로 바꿔주는 거예요!!