입력 : 연산할 수열, 연산자별 사용 가능한 갯수
출력 : 연산 결과로 나온 경우의 수 중에서 최대값과 최솟값
풀이
1. 재귀함수 한 번은 배열의 숫자 사이에 연산자를 하나 넣어본 것과 같다.
2. 함수를 한번 호출해 연산자를 넣어 계산한 뒤 재귀호출
3. 수열의 맨 마지막 수를 지나치면 전역변수 maxR과 minR을 연산 결과값이랑 비교해 갱신하고 return.
4. 연산자 사용시 opSymbol에 남은 횟수를 갱신해야 함
소스코드
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
48
49
50
51
52
53
54
55 |
#include <iostream>
using namespace std;
int N;
int opSymbol[4];
int maxR, minR;
int arr[12];
void calcOne(int n, int median){
if(n == N){
if(maxR < median)
maxR = median;
if(minR > median)
minR = median;
}
for(int i=0; i<4; i++){
if(opSymbol[i] == 0)
continue;
opSymbol[i]--;
switch(i){
case 0:
calcOne(n+1, median+arr[n]);
break;
case 1:
calcOne(n+1, median-arr[n]);
break;
case 2:
calcOne(n+1, median*arr[n]);
break;
case 3:
calcOne(n+1, median/arr[n]);
break;
}
opSymbol[i]++;
}
}
int main() {
cin>>N;
for(int i=0; i<N; i++)
cin>>arr[i];
cin>>opSymbol[0]>>opSymbol[1]>>opSymbol[2]>>opSymbol[3];
maxR = -2000000000;
minR = 2000000000;
calcOne(1, arr[0]);
cout<<maxR<<endl;
cout<<minR<<endl;
return 0;
} |
cs |
'개발 > 알고리즘' 카테고리의 다른 글
백준 알고리즘 15686 (0) | 2019.04.12 |
---|---|
백준 알고리즘 15685 (0) | 2019.04.12 |
백준 알고리즘 14503 (0) | 2019.02.21 |
백준 알고리즘 14891 (0) | 2019.02.20 |
백준 알고리즘 1673 (0) | 2019.02.20 |