[SW Expert Academy] 4008. [모의 SW 역량테스트] 숫자 만들기

문제의 저작권은 SW Expert Academy에 있습니다.

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

SW Expert Academy

선표는 게임을 통해 사칙 연산을 공부하고 있다.

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개]의 연산자 카드가 주어진 경우를 생각해보자.

[Figure 1]

 

아래 [Table 1]은 만들 수 있는 수식과 계산 결과이다.

                   

수식	수식의 계산 결과
3 + 5 + 3 - 7 / 9	0
3 + 5 + 3 / 7 - 9	-8
3 + 5 - 3 + 7 / 9	1
3 + 5 - 3 / 7 + 9	9
3 + 5 / 3 + 7 - 9	0
3 + 5 / 3 - 7 + 9	4
3 / 5 + 3 + 7 - 9	1
3 / 5 + 3 - 7 + 9	5
3 / 5 - 3 + 7 + 9	13
3 - 5 + 3 + 7 / 9	0
3 - 5 + 3 / 7 + 9	9
3 - 5 / 3 + 7 + 9	16

                                   [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 부터 시작하는 테스트 케이스의 번호이다. )

정답은 연산자 카드를 사용하여 만들 수 있는 수식으로 얻은 결과값 중 최댓값과 최솟값의 차이이다.

 

---

주의) python나누기

음수 값을 양수값으로 나눌떄 우리가 생각한 것처럼 나오지 않는다. 따라서 아래의 예를 참고하여 코드를 작성하자.

a, b = -3, 2
print(a//b)            # -2
print(int(a/b))        # -1

그러면 어떻게 작성해야하지? 아래부분을 보자. python에서는 print(int(a/b))로 해도되지만, 다른언어랑 통일감을 가지기 위해서는 아래처럼 작성을한다.

if a<0:
    print(-(abs(a)//b))    # -1
else:
    print(a//b)

풀이

def f(n, k, r, op1, op2, op3, op4):
    global minV, maxV
    if n ==k:
        if maxV< r:
            maxV = r
        if minV > r:
            minV = r
    else:
        if op1>0:
            f(n+1, k, r+card[n], op1-1, op2, op3, op4)
        if op2>0:
            f(n+1, k, r-card[n], op1, op2-1, op3, op4)
        if op3>0:
            f(n+1, k, r*card[n], op1, op2, op3-1, op4)
        if op4>0:
            f(n+1, k, int(r/card[n]), op1, op2, op3, op4-1)

TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    op1, op2, op3, op4 = map(int, input().split())
    card = list(map(int, input().split()))
    minV = 10000000000
    maxV = -10000000000
    f(1, N, card[0], op1, op2, op3, op4)
    print('#{} {}'.format(tc, maxV-minV))