백준 14888 파이썬 설명 - baegjun 14888 paisseon seolmyeong

세상을 바꾸는 데이터

문제 링크:

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

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

풀이 유형:

브루트포스 알고리즘, 백트래킹, 깊이 우선 탐색, 너비 우선 탐색

풀이 과정:

이 문제의 풀이 과정은 2가지가 있다.

★ 첫 번째 방법은 필자가 풀은 방법인 순열 라이브러리와 BFS를 이용한 방법이다.

먼저 연산자의 기호들을 차례대로 받아 순열을 이용해 가능한 모든 경우의 수를 계산하여 큐에 삽입한다.

(예를 들어 '+', '-', '+', 'x' 4가지 연산자가 있다면 24가지(=4!) 경우의 수를 모두 비교한다.)

이후에 완전탐색을 이용해 큐에서 하나씩 꺼내어 계산하고 이를 최댓값과 최솟값과 비교 후 값을 업데이트해준다.

이 방법의 단점은 시간 복잡도가 많이 소요되므로 PyPy3에서만 성공이 되고, Python3에서는 시간 초과가 뜬다.

★★ 두 번째 방법은 파이썬의 라이브러리를 사용하지 않고 DFS로만 푸는 방법이다.

DFS로 이용하는 방법은 첫 번째 방법보다 시간복잡도가 훨씬 낮으며, 모범 답안에 속한다. 

DFS 매서드 함수에 입력받은 수열의 개수만큼 계속 반복해서 재귀적으로 함수를 수행하면 된다.

첫 번째 줄의 메모리와 시간은 두 번째 방법인 DFS를 이용한 방법이며. 시간은 112ms로 Python3에서 원활하게 작동된다.

반면 두 번째 줄의 순열과 BFS를 이용한 방법은 PyPy3에서만 작동되며, 시간복잡도가 2888ms로 상당히 많이 소요됨을 알 수 있다.

풀이 코드:

첫 번째 방법: 순열과 BFS 이용

# 14888번 연산자 끼워 놓기

# 파이썬에서의 순열 라이브러리 이용
from itertools import permutations
from collections import deque

n = int(input())
seq = list(map(int, input().split()))

# 연산자 
cal = ['+', '-', '*', '//']
# 연산자 입력받기
cal_input = list(map(int, input().split()))
cal_list = []

# 계산할 수 있는 연산자
for i in range(4):
  # 특정 연산자가 존재하지 않는다면 패스
  if cal_input[i] == 0:
    pass
  # 특정 연산자가 존재한다면 그 개수만큼 계산 리스트에 추가
  else:
    for j in range(cal_input[i]):
      cal_list.append(cal[i])

# 만들 수 있는 모든 연산자 배열의 경우의 수
num_case = list(permutations(cal_list, len(cal_list)))
q = deque(num_case)

# 최댓값, 최솟값 초기화
max_result = -1e9
min_result = 1e9

# 큐가 빌 때까지 모든 경우의 수에 대해 연산 수행
while q:
  # 연산자들에 대하여 
  now_list = q.popleft()
  result = seq[0]
  # 차례로 연산 수행
  for i in range(1, len(seq)):
    # 연산자가 더하기라면
    if now_list[i-1] == '+':
      result += seq[i]
    # 연산자가 빼기라면
    elif now_list[i-1] == '-':
      result -= seq[i]
    # 연산자가 곱하기라면
    elif now_list[i-1] == '*':
      result *= seq[i]
    # 연산자가 나누기라면
    else:
      if result < 0:
        result = -(abs(result) // seq[i])
      else:
        result = result // seq[i]    
  # 최댓값, 최솟값 계산      
  max_result = max(max_result, result)
  min_result = min(min_result, result)

# 결과 출력
print(max_result)
print(min_result)

두 번째 방법: DFS 이용

# 14888번 연산자 끼워 놓기
# dfs 이용

# 수의 개수 입력받기
n = int(input())
# 수열 입력받기
data = list(map(int, input().split()))
# 연산자 개수 계산
add, sub, mul, div = map(int, input().split())

# 최댓값과 최솟값 초기화
max_value = -1e9
min_value = 1e9

# dfs 매서드 정의
def dfs(i, arr):
  global add, sub, mul, div, max_value, min_value
  # 주어진 수열을 다 받았을 경우 최댓값과 최솟값 계산
  if i == n:
    max_value = max(max_value, arr)
    min_value = min(min_value, arr)
  else:
    # 더하기
    if add > 0:
      add -= 1
      dfs(i+1, arr + data[i])
      add += 1
    # 빼기
    if sub > 0:
      sub -= 1
      dfs(i+1, arr - data[i])
      sub += 1
    # 곱하기
    if mul > 0:
      mul -= 1
      dfs(i+1, arr * data[i])
      mul += 1
    # 나누기
    if div > 0:
      div -= 1
      dfs(i+1, int(arr / data[i]))
      div += 1
  
# DFS 메서드 호출
dfs(1, data[0])

# 최댓값과 최솟값 출력
print(max_value)
print(min_value)

문제 설명

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

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

주어진 숫자와 연산자로 만들 수 있는 수식의 결과값 중 최대값과 최소값을 구하면 됩니다.

풀이 과정

이 문제는 DFS와 백트래킹을 이용했다.

문제에서 연산에 사용할 숫자(A1,A2...An)와 연산자의 개수(b1, b2, b3, b4)가 주어진다.

연산자는 앞에서 부터 차례대로 더하기, 빼기, 곱하기, 나누기 연산자의 개수를 나타낸다

숫자의 순서는 바뀌면 안되며, 연산자의 순서만을 바꿀 수 있다.

따라서, 숫자의 순서는 유지한채 연산자를 더하기, 빼기, 곱하기, 나누기를 써가며 식을 바꿔주면 되므로

첫 번째 숫자에 첫 연산자를 넣고 DFS를 돌린다음

다시 백트래킹을 통해 원래 상태로 돌린 후

두 번째 연산자를 넣고 DFS를 돌린다음 다시 백트래킹으로 원래 상태로 돌려

모든 경우의 수를 찾아내야 한다.

그리고 이 모든 경우의 수 중에 최댓값과 최솟값을 찾아 출력하면 된다.

이를 파이썬 코드로 나타내면 다음과 같다.

n = int(input())
number = list(map(int, input().split()))
op = list(map(int, input().split()))
minR = int(1e9)
maxR = -int(1e9)

answer = number[0]

def dfs(idx):
    global answer
    global minR, maxR

    if idx == n:
        if answer > maxR:
            maxR = answer
        if answer < minR:
            minR = answer
        return

    for i in range(4):
        tmp = answer
        if op[i] > 0:
            if i == 0:
                answer += number[idx]
            elif i == 1:
                answer -= number[idx]
            elif i == 2:
                answer *= number[idx]
            else:
                if answer >= 0:
                    answer //= number[idx]
                else:
                    answer = (-answer // number[idx]) * -1

            op[i] -= 1
            dfs(idx+1)
            answer = tmp
            op[i] += 1


dfs(1)
print(maxR)
print(minR)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !