BOJ(백준) 14888[연산자 끼워넣기]

 

이번 글에서는 백준 14888번 문제인 “연산자 끼워넣기”를 함께 해결해 보겠습니다. 이 문제는 주어진 수들과 연산자를 사용하여 만들 수 있는 최대값과 최소값을 구하는 문제입니다.

 

문제 URL : https://www.acmicpc.net/problem/14888

 

1. 문제 설명

1) 문제 개요

• 여러 개의 수가 주어지고, 이 수들 사이에 연산자를 끼워 넣어야 합니다.

• 사용할 수 있는 연산자는 덧셈, 뺄셈, 곱셈, 나눗셈입니다.

• 모든 가능한 연산의 조합을 탐색하여 만들 수 있는 결과의 최대값과 최소값을 구합니다.

 

2) 입력

• 첫 번째 줄에 수의 개수 N이 주어집니다. (2 ≤ N ≤ 11)

• 두 번째 줄에 N개의 수가 주어집니다. (1 ≤ 수 ≤ 100)

• 세 번째 줄에 덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수가 차례대로 주어집니다.

 

3) 출력

• 만들 수 있는 결과의 최대값과 최소값을 출력합니다.

 

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 수의 개수 N을 입력받습니다.

• 두 번째 줄에서 N개의 수를 리스트로 입력받습니다.

• 세 번째 줄에서 덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수를 차례대로 입력받습니다.

 

2) 모든 경우의 수 탐색

• 재귀 함수를 사용하여 모든 가능한 연산의 조합을 탐색합니다.

• 각 연산자에 대해 남아 있는 개수를 확인하고, 사용할 수 있는 경우 재귀 호출을 합니다.

• 재귀 호출을 통해 모든 수를 사용한 경우 결과를 최대값과 최소값으로 갱신합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 첫째 줄에 수의 개수 N을 입력받음
N = int(input().strip())

# 둘째 줄에 N개의 수를 리스트로 입력받음
arr = list(map(int, input().strip().split()))

# 셋째 줄에 덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수를 입력받음
A, B, C, D = map(int, input().strip().split())

# 결과를 저장할 변수들을 초기화
maxAns = -1000000000  # 최대값을 저장할 변수
minAns = 1000000000   # 최소값을 저장할 변수

# 재귀 함수를 정의하여 모든 경우의 수를 탐색
def rec(n, sm, a, b, c, d):
    global maxAns
    global minAns

    if sm > 1000000000 or sm < -1000000000:
        return

    # 종료 조건: 모든 수를 사용한 경우
    if n == N:
        maxAns = max(maxAns, sm)  # 최대값 갱신
        minAns = min(minAns, sm)  # 최소값 갱신
        return
    
    # 각 연산자를 사용할 수 있는지 체크하고, 사용할 수 있으면 재귀 호출
    if a > 0:  # 덧셈 연산자가 남아 있는 경우
        rec(n+1, sm+arr[n], a-1, b, c, d)
    if b > 0:  # 뺄셈 연산자가 남아 있는 경우
        rec(n+1, sm-arr[n], a, b-1, c, d)
    if c > 0:  # 곱셈 연산자가 남아 있는 경우
        rec(n+1, sm*arr[n], a, b, c-1, d)
    if d > 0:  # 나눗셈 연산자가 남아 있는 경우
        rec(n+1, int(sm/arr[n]), a, b, c, d-1)  # 나눗셈은 정수 나눗셈을 사용

# 재귀 함수 호출을 시작, 첫 번째 수는 이미 사용한 것으로 처리
rec(1, arr[0], A, B, C, D)
print(maxAns)
print(minAns)

 

4. 코드 설명

 

1) 입력 받기

• 첫째 줄에서 수의 개수 N을 입력받습니다.

• 둘째 줄에서 N개의 수를 리스트로 입력받습니다.

• 셋째 줄에서 덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수를 차례대로 입력받습니다.

 

2) 모든 경우의 수 탐색

• 재귀 함수를 사용하여 모든 가능한 연산의 조합을 탐색합니다.

• 각 연산자에 대해 남아 있는 개수를 확인하고, 사용할 수 있는 경우 재귀 호출을 합니다.

• 재귀 호출을 통해 모든 수를 사용한 경우 결과를 최대값과 최소값으로 갱신합니다.

 

3) 결과 출력

• 최종적으로 최대값과 최소값을 출력합니다.

 

3) 예시와 시각적 설명

 

예시

예를 들어, 아래와같이 입력값이 주어진다고 생각하고 진행을 해보겠습니다.

 

N = 3

arr = [3, 4, 5]

A = 1

B = 0

C = 1

D = 0

 

이 경우, 가능한 연산은 다음과 같습니다:

 

• 3 + 4 * 5

• 3 * 4 + 5

 

첫 번째 연산의 결과는 23이고, 두 번째 연산의 결과는 17입니다. 따라서 최대값은 23이고 최소값은 17이 됩니다.

 

시각적 설명

재귀 함수 rec의 호출 흐름은 다음과 같습니다

rec(1, 3, 1, 0, 1, 0)

    ├── rec(2, 7, 0, 0, 1, 0)  # 3 + 4

     │       └── rec(3, 35, 0, 0, 0, 0)  # 7 * 5

    └── rec(2, 12, 1, 0, 0, 0)  # 3 * 4

            └── rec(3, 17, 0, 0, 0, 0)  # 12 + 5

 

이 흐름을 통해 모든 가능한 연산 조합을 탐색하여 최대값과 최소값을 찾습니다.

 

5. Github으로 확인

 

coTest/BOJ/BOJ01_07_04_14888.py at main · pcy4196/coTest