[모의 SW 역량테스트] 4008 숫자 만들기 (Python)
출처
| https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH |
문제
선표는 게임을 통해 사칙 연산을 공부하고 있다.
N개의 숫자가 적혀 있는 게임 판이 있고, +, -, x, / 의 연산자 카드를 숫자 사이에 끼워 넣어 다양한 결과 값을 구해보기로 했다.
수식을 계산할 때 연산자의 우선 순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다.
예를 들어 1, 2, 3 이 적힌 게임 판에 +와 x를 넣어 1 + 2 * 3을 만들면 1 + 2를 먼저 계산하고 그 뒤에 * 를 계산한다.
즉 1+2*3의 결과는 9이다.
주어진 연산자 카드를 사용하여 수식을 계산했을 때 그 결과가 최대가 되는 수식과 최소가 되는 수식을 찾고, 두 값의 차이를 출력하시오.
[예시]
[Figure 1] 과 같이 [3,5,3,7,9]가 적힌 숫자판과 [‘+’ 2개, ‘-‘ 1개, ‘/’ 1개]의 연산자 카드가 주어진 경우를 생각해보자.
아래 [Table 1]은 만들 수 있는 수식과 계산 결과이다.
이 경우 최댓값은 3 - 5 / 3 + 7 + 9 = 16, 최솟값은 3 + 5 + 3 / 7 - 9 = -8 이다.
즉 결과는 최댓값과 최솟값의 차이 ( 16 - ( -8 ) ) 로 24 가 답이 된다.
[제약사항]
1. 시간 제한 : 최대 50 개 테스트 케이스를 모두 통과하는 데 C / C++ / Java 모두 3 초
2. 게임 판에 적힌 숫자의 개수 N 은 3 이상 12 이하의 정수이다. ( 3 ≤ N ≤ 12 )
3. 연산자 카드 개수의 총 합은 항상 N - 1 이다.
4. 게임 판에 적힌 숫자는 1 이상 9 이하의 정수이다.
5. 수식을 완성할 때 각 연산자 카드를 모두 사용해야 한다..
6. 숫자와 숫자 사이에는 연산자가 1 개만 들어가야 한다.
7. 완성된 수식을 계산할 때 연산자의 우선 순위는 고려하지 않고, 왼쪽에서 오른쪽으로 차례대로 계산한다.
8. 나눗셈을 계산 할 때 소수점 이하는 버린다.
9. 입력으로 주어지는 숫자의 순서는 변경할 수 없다.
10. 연산 중의 값은 -100,000,000 이상 100,000,000 이하임이 보장된다.
[입력]
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,
그 다음 줄부터 T 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N 이 주어진다.
다음 줄에는 '+', '-', '*', '/' 순서대로 연산자 카드의 개수가 공백을 사이에 두고 주어진다.
다음 줄에는 수식에 들어가는 N 개의 숫자가 순서대로 공백을 사이에 두고 주어진다.
[출력]
테스트 케이스 개수만큼 T 개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 "#t" 로 시작하고 공백을 하나 둔 다음 정답을 출력한다. ( t 는 1 부터 시작하는 테스트 케이스의 번호이다. )
정답은 연산자 카드를 사용하여 만들 수 있는 수식으로 얻은 결과값 중 최댓값과 최솟값의 차이이다.
입력
|
10 // 총 테스트 케이스의 개수 T = 10 5 // 첫 번째 테스트 케이스, N = 5 본문 예제 2 1 0 1 // 각 연산자의 개수 '+' 2 개, '-' 1 개, '*' 0 개, '/' 1 개 3 5 3 7 9 // 수식에 사용되는 숫자 6 // 두 번째 테스트 케이스, N = 6 4 1 0 0 // 각 연산자의 개수 '+' 4 개, '-' 1 개, '*' 0 개, '/' 0 개 1 2 3 4 5 6 // 수식에 사용되는 숫자 … // 나머지는 sample_input.txt 참조 |
#1 24 #2 8 #3 144 #4 8 #5 91 #6 150 #7 198 #8 2160 #9 46652 #10 701696 |
풀이
연산자에 대해서 DFS탐색을 통해 숫자와 계산해 나가며 최대값과 최소값 계산하면 된다.
주의할 점으로는 나눗셈 계산인데, 음수를 나눗셈 할 때 문제가 발생하게 된다.
아래는 내가 시행착오를 거쳤던 내용이다.
1. // 연산자를 사용했지만 -2 // 3 의 경우 내가 원하는 숫자는 -1인데 -2가 나오는 결과가 나오게 된다.
2. 그래서 음수 양수로 나눴으며 음수의 경우에는 +1을 줘봤지만.... 또 틀리단다. 생각해보니 소숫점 없이 딱 떨어지는 경우에는 +1을 하면 안되는데 더해줘서 그런거 같다
3. 그래서 마지막으로는 int형 씌웠다. int형 자체가 소숫점이 생기면 버림을 취하기에 시도해 보았고 다행히 이번에는 Pass를 할 수 있었다.
코드
|
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
|
def dfs(idx,result):
global max_num
global min_num
if idx == N-1: # 연산은 주어진 숫자보다 1번 적으므로 N-1까지 탐색
if max_num <= result:
max_num = result
if result <= min_num:
min_num = result
return
for i in range(4): # 연산 4번 만큼 반복
if moderator[i] > 0: # 연산자가 존재한다면
moderator[i] -= 1 # 해당 연산자를 한번 사용한다는 뜻
if i == 0:
new_result = result + number[idx+1]
elif i == 1:
new_result = result - number[idx+1]
elif i == 2:
new_result = result * number[idx+1]
else: # 나눗셈의 경우 음수 나눗셈 때문에 주의가 필요함. int형을 통해 버림을 취함
new_result = int(result / number[idx+1])
dfs(idx+1,new_result)
moderator[i] += 1
T = int(input())
for t in range(T):
N = int(input())
moderator = list(map(int,input().split())) # [+ - * /]순으로 저장
number = list(map(int,input().split()))
max_num = -9999990
min_num = 99999999
dfs(0,number[0])
print('#{} {}'.format(t+1,max_num-min_num))
|