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

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH

SW Expert Academy

 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

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

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

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

 

 

입력

10 5 2 1 0 1 3 5 3 7 9 6 4 1 0 0 1 2 3 4 5 6 …

// 총 테스트 케이스의 개수 T = 10 // 첫 번째 테스트 케이스, N = 5 본문 예제 // 각 연산자의 개수 '+' 2 개, '-' 1 개, '*' 0 개, '/' 1 개 // 수식에 사용되는 숫자 // 두 번째 테스트 케이스, N = 6 // 각 연산자의 개수 '+' 4 개, '-' 1 개, '*' 0 개, '/' 0 개 // 수식에 사용되는 숫자 // 나머지는 sample_input.txt 참조

출력

#1 24 #2 8 #3 144 #4 8 #5 91 #6 150 #7 198 #8 2160 #9 46652 #10 701696

 

 

 

와 진짜 얼마만의 블로그인가.. 

포트폴리오 만든다는 핑계로 다 내팽겨치고 공부를 안함 ㅠ_ㅠ 

먼저 처음에 문제 접근 할 때 

재귀함수는 생각도 못하고 머리속에 있는 딕셔너리랑 순열 조합 온갖 지식들을 동원해서

아주 하드코딩을 했는데 test case 35개를 맞음 .. ㅋㅋㅋㅋㅋㅋ

코드길이도 어마 어마 

아무리 풀려고 해도 풀리질 않아서 문제풀이 보고 따라 풀었음. 

 

결국 이건 재귀를 사용해서 푸는거였더라

ㅠ

 

근데 진짜 따라서 푸는데도 결과값이 이상해서 머리가 좀 아팠음.. 

return 을 하면 함수가 끝나는데 return 을 써서 자꾸 min, max값이 0이 나옴.  

 

일단 함수설명을 하자면

n은 num의 인덱스 이고

k는 num의 값을 다 돌았을때 끝내야 하니까 num의 길이로 보면 된다.

r 은 num 배열의 숫자와 수식을 이용하여 계산한 값을 누적시켜주는 변수쯤으로 보면 된다. 

수식을 a,b,c,d로 받은 다음에 그 수식을 사용하면 -1을 해주는 방법이다. 

a는 +, b는 -, c는 *, d는 / 이다. 

 

처음 r은 num[0]으로 시작하고 첫번째 값과 그 다음값을 계산해주어야 한다.

그래서 n은 1부터 시작한다.

 

최대값 최소값의 차이를 구하라고 했기 때문에

global 변수에 최대값(maxV), 최소값(minV)을 선언해 준뒤 누적된 r 의 값이 

maxV보다 크면 maxV 값을 r로 바꿔주고

마찬가지로 최소값보다 작으면 minV 값을 r로 바꿔준다. 

 

제약사항에 

연산 중의 값은 -100,000,000 이상 100,000,000 이하임이 보장된다.

라는 부분이 있기 때문에 minV 를 -10000000000 minV를 10000000000 로 지정함.

def multi(n, k,r,a,b,c,d):
    global minV, maxV
    if n==k:
        if maxV<r:
            maxV = r
        if minV>r:
            minV = r
    else:
        if a>0:
            multi(n+1, k, r+num[n], a-1,b,c,d)
 
        if b>0:
            multi(n+1, k, r-num[n], a,b-1,c,d)
        if c>0:
            multi(n+1, k, r*num[n], a,b,c-1,d)
        if d>0:
            multi(n+1, k, int(r/num[n]), a,b,c,d-1)
        
 
t= int(input())
for t in range(1, t+1):
    N = int(input())
    a,b,c,d =map(int, input().split()) # 연산자의 개수 
    num = list(map(int, input().split())) #수식에 사용되는 숫자
    minV = 10000000000
    maxV = -10000000000
    multi(1,N, num[0], a,b,c,d )
    print('#{} {}'.format(t, maxV-minV))