개발 학습 블로그입니다.

3 minute read

백준 문제 중 14888번

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

문제

N개의 수로 이루어진 수열 A1, A2, …, AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

  • 1+2+3-4×5÷6
  • 1÷2+3+4-5×6
  • 1+2÷3×4-5+6
  • 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

  • 1+2+3-4×5÷6 = 1
  • 1÷2+3+4-5×6 = 12
  • 1+2÷3×4-5+6 = 5
  • 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

Try1

DFS 로 순열을 만들고 모든 순열의 경우대해 완전탐색으로 풀이

from pprint import pprint
n = int(input())
m = n-1
operands = list(input().split())
nums_operators = list(map(int,input().split()))
all_operators = ['+']*nums_operators[0]+['-']*nums_operators[1]+['*']*nums_operators[2]+['/']*nums_operators[3]


visited = [False]*m
tmp = []
operators = []

def dfs():

    if len(tmp)==m:
        operators.append(tmp[:])
        return

    for i in range(m):
        if not visited[i]:
            visited[i] = True
            tmp.append(all_operators[i])
            dfs()
            tmp.pop()
            visited[i] = False

dfs()
# pprint(operators)
results = []


for operator in operators:
    s = '' + str(operands[0])
    for i in range(m):
        s = str(int(eval(s+operator[i]+operands[i+1])))
    results.append(int(s))

print(max(results))
print(min(results))

6
1 2 3 4 5 6
2 1 1 1
54
-24

예제의 입력에 대한 출력은 모두 맞았으나, 시간 초과가떴다. 완전탐색 부분에 최적화가 더 필요해 보였다.

Try2

DFS 에서 백트래킹을 통해 완전탐색

순열을 구하는 과정과 최대 최소를 구하는 과정을 하나로 합쳐서 DFS 함수를 구성하면 시간초과가 해결됐다.

코드의 흐름은 이렇다.

  • 재귀적으로 숫자들과 연산을 조합할 함수 dfs(depth, total, plus, minus, mul, div) 를 선언한다.

  • depth 는 백트래킹을 위한 변수, total은 지금까지의 연산의 총 합을 저장할 변수, 그리고 각각의 남은 연산 횟수 저장할 변수로 plus, minus, mul, div 설정한다.
  • dfs의 내부에서 여러개의 출발점을 가지는 DFS 를 시작 시킨다. 각각 plus 부터 하는 경우, minus 부터 하는 경우, mul 부터 하는 경우, div 부터 하는 경우를 뜻하고 재귀 호출되며 모든 순열 경우의 total을 depth가 n과 같을때 results에 담고, return으로 종료한다.
import sys

n = int(input())
nums = list(map(int,input().split()))
operators = list(map(int,input().split()))

 # 모든 경우의 연산의 각각을 담을 변수 results 선언
results = []

 # 모든 연산을 재귀적으로 진행할 함수 dfs 선언 
def dfs(depth:int, total:int, plus:int, minus:int, mul:int, div:int)->None:

     # depth 가 n일경우 results에 total을 담고 종료
    if depth == n:
        results.append(total)
        return

     # 이번 depth에 '+' 연산부터 할 경우의 재귀
    if plus:
        dfs(depth+1,total+nums[depth], plus-1, minus, mul, div)

     # 이번 depth에 '-' 연산부터 할 경우의 재귀
    if minus:
        dfs(depth+1,total-nums[depth], plus, minus-1, mul, div)

     # 이번 depth에 '*' 연산부터 할 경우의 재귀    
    if mul:
        dfs(depth+1,total*nums[depth], plus, minus, mul-1, div)

     # 이번 depth에 '/' 연산부터 할 경우의 재귀
     # int로 감싸줌
    if div:
        dfs(depth+1,int(total/nums[depth]), plus, minus, mul, div-1)


plus, minus, mul, div = operators
dfs(1,nums[0],plus,minus,mul,div)

 # 최대값과 최소값 출력
print(max(results))
print(min(results))


6
1 2 3 4 5 6
2 1 1 1
54
-24

어떻게 해결할지 고민을 많이 했는데, 막상 검색을 해보니 생각보다 코드도 간결하고 쉬운 문제였던거 같다.

Leave a comment

You may also enjoy