문제출처 : https://www.acmicpc.net/problem/14888
1. 문제요약
- N개의 수로 이루어진 수열 A1, A2, ... , An이 주어진다.
- 수 사이에 끼워 넣을 연산자가 N-1개 주어진다.
- 수의 순서는 고정되어 있고 숫자 사이에 연산자를 넣어서 만들 수 있는 최대값과 최솟값을 출력
- 수식은 +, -, *, / 순이다.
- 2 <= N <= 11
2. 접근방법
- 조합!
- 10! / (덧셈 연산자 갯수)! * (뺄셈 연산자 갯수)! * (곱셈 연산자 갯수)! * (나눗셈 연산자 갯수)!
3. 시간복잡도
- 10! / (덧셈 연산자 갯수)! * (뺄셈 연산자 갯수)! * (곱셈 연산자 갯수)! * (나눗셈 연산자 갯수)!
4. 회고
- 문제에서 음수 / 양수 인 경우 음수를 양수로 바꾸고 나눗셈 연산을 한 뒤에 다시 음수를 붙이라고 해서
진짜 그렇게 했는데.. 굳이 그렇게 안해도 그냥 그런식으로 연산이 되는거였네...
- 종만북에 조합관련된 비슷한 문제가 있었던거 같은데... 찾아봐야지
- 처음에 long long 로 max값을 -2e31 / min값을 2e31-1 로 잡았는데 왜 값이 제대로 안들어가지??
- 아.. 음... 엄청 멍청했군.... 2e31 은 2뒤에 0이 31개 있다는 뜻인데 왜 2^31으로 생각했지 ㅋㅋ
소스코드
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 | #include<iostream>
using namespace std;
int n, a[12], s[4];
long long ans_max = -1000000000, ans_min = 1000000000;
void dfs( int cnt, int sum){
if (cnt == n - 1){
if (sum < ans_min)
ans_min = sum;
if (ans_max < sum)
ans_max = sum;
return ;
}
if (s[0] > 0){
s[0]--;
dfs(cnt + 1, sum + a[cnt + 1]);
s[0]++;
}
if (s[1] > 0){
s[1]--;
dfs(cnt + 1, sum - a[cnt + 1]);
s[1]++;
}
if (s[2] > 0){
s[2]--;
dfs(cnt + 1, sum * a[cnt + 1]);
s[2]++;
}
if (s[3] > 0){
s[3]--;
dfs(cnt + 1, sum / a[cnt + 1]);
s[3]++;
}
}
int main( void ){
cin >> n;
for ( int i = 0; i < n; i++)
cin >> a[i];
for ( int i = 0; i < 4; i++)
cin >> s[i];
dfs(0, a[0]);
cout << ans_max << "\n" ;
cout << ans_min << "\n" ;
}
|
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]