[SWEA]숫자 만들기 - 4008 (모의 역량 테스트)
| 시간 제한 | 메모리 제한 |
|---|---|
| 10 초 | 힙 정적 메모리: 256 MB / 스택 메모리 1MB |
문제
선표는 게임을 통해 사칙 연산을 공부하고 있다.
N개의 숫자가 적혀 있는 게임 판이 있고, +, -, x, / 의 연산자 카드를 숫자 사이에 끼워 넣어 다양한 결과 값을 구해보기로 했다.
수식을 계산할 때 연산자의 우선 순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다.
예를 들어 1, 2, 3 이 적힌 게임 판에 +와 x를 넣어 1 + 2 * 3을 만들면 1 + 2를 먼저 계산하고 그 뒤에 * 를 계산한다.
즉 1+2*3의 결과는 9이다.
주어진 연산자 카드를 사용하여 수식을 계산했을 때 그 결과가 최대가 되는 수식과 최소가 되는 수식을 찾고, 두 값의 차이를 출력하시오.
자세한 예시는 여기로
제약 사항
시간 제한 : 최대 50 개 테스트 케이스를 모두 통과하는 데 C / C++ / Java 모두 3 초
게임 판에 적힌 숫자의 개수 N 은 3 이상 12 이하의 정수이다. ( 3 ≤ N ≤ 12 )
연산자 카드 개수의 총 합은 항상 N - 1 이다.
게임 판에 적힌 숫자는 1 이상 9 이하의 정수이다.
수식을 완성할 때 각 연산자 카드를 모두 사용해야 한다..
숫자와 숫자 사이에는 연산자가 1 개만 들어가야 한다.
완성된 수식을 계산할 때 연산자의 우선 순위는 고려하지 않고, 왼쪽에서 오른쪽으로 차례대로 계산한다.
나눗셈을 계산 할 때 소수점 이하는 버린다.
입력으로 주어지는 숫자의 순서는 변경할 수 없다.
연산 중의 값은 -100,000,000 이상 100,000,000 이하임이 보장된다.
입력
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,
그 다음 줄부터 T 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N 이 주어진다.
다음 줄에는 ‘+’, ‘-‘, ‘*’, ‘/’ 순서대로 연산자 카드의 개수가 공백을 사이에 두고 주어진다.
다음 줄에는 수식에 들어가는 N 개의 숫자가 순서대로 공백을 사이에 두고 주어진다.
출력
테스트 케이스 개수만큼 T 개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 “#t” 로 시작하고 공백을 하나 둔 다음 정답을 출력한다. ( t 는 1 부터 시작하는 테스트 케이스의 번호이다. )
정답은 연산자 카드를 사용하여 만들 수 있는 수식으로 얻은 결과값 중 최댓값과 최솟값의 차이이다.
풀이
주어진 숫자 사이에 주어진 연산자를 넣어 수를 계산하고, 그 수의 최대와 최소의 차이를 출력하는 문제이다.
무심코 풀이를 생각하면 받은 연산자를 모든 위치에 넣어가면서 계산하면 되는 것이 아닌가 할 수 있지만, 이 경우 중복 계산이 빈번하게 발생할 수 있다.
예를 들어 + + + 로 연산자가 주어진다면 어떤 경우이든 같은 값이 나올 것이다. 하지만 연산자를 모든 위치에 넣어가면서 계산할 경우 $3 * 2 * 1 = 6$ 번의 중복 계산을 하게 된다.
이런 경우를 방지하기 위해 연산자의 수를 세는 딕셔너리를 만들고, 몇 번 사용했는지 확인하였다. 이렇게 하면 각 연산자마다 다른 것으로 생각하지 않기 때문에 위에서 언급한 중복 연산을 없앨 수 있다.
코드
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
43
44
45
46
47
# 계산
def calculate(num1, num2, operator):
if operator == '+':
num1 += num2
elif operator == '-':
num1 -= num2
elif operator == '*':
num1 *= num2
elif operator == '/':
num1 = int(num1 / num2)
return num1
# 수식 완성
def search_expression(i, result):
if i == n:
global max_num, min_num
max_num = max(max_num, result)
min_num = min(min_num, result)
return
for operator in operators:
if operator_dict[operator] > 0:
operator_dict[operator] -= 1
search_expression(i + 1, calculate(result, nums[i+1], operator))
operator_dict[operator] += 1
test_case = int(input())
for t in range(test_case):
n = int(input()) - 1
operators = ['+', '-', '*', '/']
operator_dict = {operator: cnt for operator, cnt in zip(operators, map(int, input().split()))}
nums = list(map(int, input().split()))
max_num = float('-inf')
min_num = float('inf')
result_dict = {}
visited = []
search_expression(0, nums[0])
print(f"#{t + 1} {max_num - min_num}")