각 연산기호의 개수를 입력받고 나서,
모든 순서를 인덱스를 통해서 순열로 만들고
하나하나 계산해보면서 Max, Min값 기록해서 계산하자
N개의 숫자가 적혀 있는 게임 판이 있고,
+, -, x, / 의 연산자 카드를 숫자 사이에 끼워 넣어 다양한 결과 값을 구해보기로 했다.
수식을 계산할 때 연산자의 우선 순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다.
주어진 연산자 카드를 사용하여 수식을 계산했을 때
그 결과가 최대가 되는 수식과 최소가 되는 수식을 찾고,
두 값의 차이를 출력하시오.
[제약사항]
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 이하임이 보장된다.
[입력]
각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N 이 주어진다.
다음 줄에는 '+', '-', '*', '/' 순서대로 연산자 카드의 개수가 공백을 사이에 두고 주어진다.
다음 줄에는 수식에 들어가는 N 개의 숫자가 순서대로 공백을 사이에 두고 주어진다.
[출력]
정답은 연산자 카드를 사용하여 만들 수 있는 수식으로 얻은 결과값 중
최댓값과 최솟값의 차이이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int acc[4];
int map[15];
vector<int>calc;
void DFS(int now, int cnt) {
if (cnt == N) {
calc.push_back(now);
return;
}
if (acc[0]) {
now += map[cnt];
cnt++;
acc[0]--;
DFS(now, cnt);
acc[0]++;
cnt--;
now -= map[cnt];
}
if (acc[1]) {
now -= map[cnt];
cnt++;
acc[1]--;
DFS(now, cnt);
acc[1]++;
cnt--;
now += map[cnt];
}
if (acc[2]) {
now *= map[cnt];
cnt++;
acc[2]--;
DFS(now, cnt);
acc[2]++;
cnt--;
now = now / map[cnt];
}
if (acc[3] && map[cnt] != 0) {
// 나머지를 먼저 계산해둬야함
int rest = now % map[cnt];
now = now / map[cnt];
cnt++;
acc[3]--;
DFS(now, cnt);
cnt--;
now = now * map[cnt] + rest;
acc[3]++;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
calc.clear();
cin >> N;
for (int i = 0; i < 4; i++) {
cin >> acc[i];
}
for (int i = 0; i < N; i++) {
cin >> map[i];
}
DFS(map[0], 1);
sort(calc.begin(), calc.end());
int ans = calc[calc.size()-1] - calc[0];
cout << "#" << tc << " " << ans << "\n";
}
return 0;
}