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개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
이 문제는 최대 11개의 수가 주여졌을때 각 수와 수 사이에 사칙연산 중 하나를 삽입하는 경우에 대하여 만들어질 수 있는 결과 값의 최대값 및 최솟값을 구하면 된다. 따라서 모든 경우의 수를 계산하기 위하여(완전 탐색) DFS혹은 BFS를 이용하여 문제를 해결 할 수 있다.
결국 이 문제는 각 사칙 연산을 중복해서 사용하는 것이 허용되기 때문에 중복 순열을 계산해야 합니다. n=4라고 하면 사칙 연산중에서 중복을 허용하여 3개를 뽑아 나열하는 모든 경우를 고려해야 합니다. 중복 순열은 product 라이브러리를 이용하여 간단하게 찾을 수 있습니다. 다만 이번에는 DFS를 이용해서 푸는 풀이입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
n = int(input())
#연산을 수행하고자 하는 수 리스트
data = list(map(int,input().split()))
#더하기, 빼기, 곱하기, 나누기 연산자 개수
add, sub, mul, div = map(int,input().split())
#최솟값과 최댓값 초기화
min_value = 1e9
max_value = -1e9
#깊이 우선 탐색(DFS) 매서드
def dfs(i, now):
global min_value, max_value, add, sub, mul, div
#모든 연산자를 다 사용한 경우, 최솟값과 최대값 업데이트
if i == n:
min_value = min(min_value, now)
max_value = max(max_value, now)
else:
#각 연산자에 대해서 재귀적으로 수행
if add > 0:
add -= 1
dfs(i+1, now+data[i])
add += 1
if sub > 0:
sub -= 1
dfs(i+1, now-data[i])
sub += 1
if mul > 0:
mul -= 1
dfs(i+1, now*data[i])
mul += 1
if div > 0:
div -= 1
dfs(i+1, int(now/data[i])) #나머지는 제거
div += 1
#DFS 매서드 호출
dfs(1, data[0])
#최댓값과 최솟값 출력
print(max_value)
print(min_value)
전체 코드는 재귀적으로 돌아가게 설정이 되어 있습니다. 한번 예시를 따라서 쭉 보겠습니다.
n = 2 숫자 5,6 data=[5,6] 연산 곱셈 1개 mul = 1 나머지 0
dfs에 1이 들어가는데 이거는 연산 횟수입니다. 당연히 첫번째니까 첫번째 연산으로 시작을 합니다. 그리고 두번째 파라미터는 현재 들어가는 숫자인데 data[0]은 왼쪽부터 순서대로 입력과 동작 수행이 이루어지게 됩니다.
i가 n(연산숫자 개수)에 도달할때까지 진행을 하게 됩니다.
그렇지 않으면 else로 넘어갑니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#각 연산자에 대해서 재귀적으로 수행
if add > 0:
add -= 1
dfs(i+1, now+data[i])
add += 1
if sub > 0:
sub -= 1
dfs(i+1, now-data[i])
sub += 1
if mul > 0:
mul -= 1
dfs(i+1, now*data[i])
mul += 1
if div > 0:
div -= 1
dfs(i+1, int(now/data[i])) #나머지는 제거
div += 1
일단 mul이 유일하게 0이 아니라 1입니다. 그러면 dfs(2, 5*6)이 들어가게 됩니다. 즉 30이 되고 i=2이고 이는 i==n이기 때문에 최솟값과 최대값을 반환하고 연산이 종료됩니다.
너무 간단한 예시이니 다른 것을 살펴봅시다.
n = 3 숫자 3, 4, 5 data=[4, 5, 6] 연산 덧셈 1개 곱셈 1개
일단 3로 시작을 하는데 가장먼저 add가 0보다 크니 이쪽으로 가봅시다. dfs(2,3+4)로 들어갑니다.
그러면 남은 것은 곱셈 연산 하나밖에 남지 않았고 mul로 가게 됩니다. dfs(3,7*5)로 들어갑니다.
이제 남은 연산이 없으니 최솟값과 최대값을 반환합니다.
다시 내려가서 mul이 0보다 크니 이쪽으로 가봅시다 dfs(2,3*4)가 됩니다. 그리고 add로 들어가면 dfs(3,12+7)이 되고 이후 가능한 연산이 없으니 최솟값과 최대값을 반환하게 되고
각각 35, 17로 연산이 종료가 됩니다.
product를 이용해서 모든 연산을 살펴볼 수도 있지만 이렇게 DFS 재귀를 이용해서도 구성할 수 있으니 확인
.. 저는 개인적으로 연산할 숫자를 넣은 스택과 연산자를 가능한 숫자를 어쩌고 했는데… 가능한 코드는 단순하고 저장복잡도는 낮게 하도록 연습 많이 해야 겠습니다.
Comments powered by Disqus.