숫자만들기 Python(SW Expert Academy, SWEA)

난이도 : 모의 SW 역량테스트

문제번호 : 4008

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

선표는 게임을 통해 사칙 연산을 공부하고 있다. 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 5 2 1 0 1 3 5 3 7 9 6 4 1 0 0 1 2 3 4 5 6 …	#1 24 #2 8 #3 144 #4 8 #5 91 #6 150 #7 198 #8 2160 #9 46652 #10 701696

---

2. 문제풀이

dfs를 이용하여 계산하면 풀리는 문제였다. 숫자 사이에 넣을 수 있는 연산자를 돌려가면서 넣어 가장 큰 값과 가장 작은 값을 찾는다. 같은 연산자가 여러개일 수 있기때문에 유의해서 코드를 작성했다. 수식의 순서는 우선순위에 두지않고 왼쪽부터 오른쪽으로 진행된다. 따라서 따로 순서를 저장해서 계산하지 않고 바로 계산해서 나가면 된다. 소수점이 발생할때는 내림처리를 해야하는 부분을 주의해야 한다.

---

3. 소스코드

# 4008 숫자 만들기
modul = ['+', '-', '*', '/']
 
def cal(a, b, _modul):
    if _modul == 0:
        return a + b
    elif _modul == 1:
        return a - b
    elif _modul == 2:
        return a * b
    #//를 하게되면 내림으로 되기때문에 버림으로 처리
    else : return int(a / b)
 
def dfs(idx, _ans):
    if idx >= N:
        global max_n, min_n
        if _ans > max_n:
            max_n = _ans
        if _ans < min_n:
            min_n = _ans
        return
    for i in range(4):
        if moduls[i]:
            moduls[i] -= 1
            dfs(idx+1, cal(_ans, numbers[idx+1], i))
            moduls[i] += 1
 
 
T = int(input())
for t in range(1, T+1):
    N = int(input()) - 1
    moduls = list(map(int, input().split()))
    max_n = -987654321
    min_n = 987654321
    numbers = list(map(int, input().split()))
    dfs(0, numbers[0])
    print('#{} {}'.format(t, max_n - min_n))