브루트 포스

interviewsangu·2020년 7월 13일
0

알고리즘

목록 보기
2/12
post-thumbnail

Brute Force

모든 경우의 수를 다 해보는 것을 브루트 포스라 한다.

  1. 문제의 가능한 경우를 계산해 O(1억)이 넘지 않는지 확인한다.
  2. 1에서 문제가 없는 경우, 가능한 모든 방법을 모두 해 본다.
    • 이때 하나의 경우라도 빠짐이 없이 해야 한다.
    • for, 순열, 재귀, Bit-mask를 이용한다.
  3. 답을 구한다.

https://www.acmicpc.net/problem/2309
일곱 난쟁이

#include <iostream>
#include <algorithm>
using namespace std;

int a[9];
int n = 9;
int main() {
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	sort(a, a + 9);
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			if (sum - a[i] - a[j] == 100) {
				for (int k = 0; k < n; k++) {
					if (k == i || k == j) continue;
					cout << a[k] << '\n';
				}
				return 0; //단 한번의 실행
			}
		}
	}
	return 0;
}

https://www.acmicpc.net/problem/1476
날짜 계산

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int e, s, m;
	cin >> e >> s >> m;

	for (int i = 0;; i++) {
		int x = i * 28 + s;
		if ((x - e) % 15 == 0 && (x - m) % 19 == 0) {
			cout << x << '\n';
			return 0;
		}
	}
	return 0;
}
#include <iostream>
using namespace std;
int main(){
	int E, S, M;
    cin >> E >> S >> M;
    int e = 1, s = 1, m = 1;
    for(int i = 1;; i++){
    	if(e == E && s == S && m == M){
        	cout << i << '\n';
            return 0;
        }
    e +=1; s += 1; m +=1;
    if(e == 16) e = 1;
    if(s == 29) s = 1;
    if(m == 20) m = 1;
    }
    return 0;
}

https://www.acmicpc.net/problem/14500
테트로미노

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	int a[500][500];
	memset(a, 0, sizeof(a));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			//1
			if (j + 3 < m) {
				int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i][j + 3];
				if (ans < temp) ans = temp;
			}
			if (i + 3 < n) {
				int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 3][j];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j + 1 < m) {
				int temp = a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j + 2 < m) {
				int temp = a[i][j] + a[i + 1][j] + a[i + 1][j + 1] + a[i + 1][j + 2];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j - 2 >= 0) {
				int temp = a[i][j] + a[i + 1][j] + a[i + 1][j - 1] + a[i + 1][j - 2];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j + 1 < m) {
				int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i + 2][j + 1];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j - 1 >= 0) {
				int temp = a[i][j] + a[i][j - 1] + a[i + 1][j - 1] + a[i + 2][j - 1];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j + 2 < m) {
				int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i + 1][j + 2];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j - 2 >= 0) {
				int temp = a[i][j] + a[i][j - 1] + a[i][j - 2] + a[i + 1][j - 2];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j + 1 < m) {
				int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 2][j + 1];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j - 1 >= 0) {
				int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 2][j - 1];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j + 2 < m) {
				int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i][j + 2];
				if (ans < temp) ans = temp;
			}
			if (i -1 >=0 && j + 2 <m) {
				int temp = a[i][j] + a[i][j + 1] + a[i - 1][j + 1] + a[i][j + 2];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && i - 1 >= 0 && j - 1 >= 0) {
				int temp = a[i][j] + a[i][j - 1] + a[i + 1][j - 1] + a[i - 1][j - 1];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && i - 1 >= 0 && j + 1 < m) {
				int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i - 1][j + 1];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j + 2 < m) {
				int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i + 1][j + 2];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j - 2 >= 0) {
				int temp = a[i][j] + a[i][j - 1] + a[i + 1][j - 1] + a[i + 1][j - 2];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j + 1 < m) {
				int temp = a[i][j] + a[i + 1][j] + a[i + 1][j + 1] + a[i + 2][j + 1];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j - 1 >= 0) {
				int temp = a[i][j] + a[i + 1][j] + a[i + 1][j - 1] + a[i + 2][j - 1];
				if (ans < temp) ans = temp;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}
#include <iostream>
using namespace std;
int a[500][500];
int block[19][3][2] = {
{{0,1}, {0,2}, {0,3}},
{{1,0}, {2,0}, {3,0}},
{{0,1}, {1,0}, {1,1}},
{{-1,0}, {-1, 1}, {-1,2}},
{{1,0}, {1,1}, {1,2}},
{{0,1}, {1,1}, {2,1}},
{{-2,1}, {-1, 1}, {0,1}},
{{1,0}, {1, -1}, {1, -2}},
{{-1,0}, {-1, -1}, {-1, -2}},
{{0, -1}, {1, -1}, {2,-1}},
{{0,-1}, {-1, -1}, {-2, -1}},
{{0,-1}, {1, -1}, {1, -2}},
{{1,0}, {1,1}, {2,1}},
{{0,1}, {1, 1}, {1,2}},
{{1,0}, {1,-1}, {2,-1}},
{{1,0}, {1,1}, {2,0}},
{{0,-1}, {1,-1}, {0,-2}},
{{0,-1}, {-1, -1}, {0, -2}},
{{1,0}, {1,-1}, {2,0}}
};

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 19; k++) {
				bool ok = true;
				int sum = a[i][j];
				for (int l = 0; l < 3; l++) {
					int x = j + block[k][l][0];
					int y = i + block[k][l][1];
					if (0 <= y && y < n && 0 <= x && x < m) {
						sum += a[y][x];
					}
					else {
						ok = false;
						break;
					}
				}
				if (ok && ans < sum) {
					ans = sum;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

대칭은 그림을 말그대로 대칭 시켜보면 된다.

순열
크기가 N인 수열은 N!개가 존재한다.
사전 순으로 다음에 오는 순열은 next_permutation, 이전 순열은 prev_permutation을 사용한다.

함수를 사용하지 않고 직접 다음 순열을 찾는 방법(이전 순열의 경우 부등호만 반대로)
(1) A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
즉, 순열의 마지막 수에서 끝나는 가장 긴 감소수열을 찾아야 한다.
(2) j >= i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.
(3) A[i-1]과 A[j]를 swap 한다.
(4) A[i] 부터 순열을 뒤집는다.

bool next_permutation(int *a, int n){
	// 감소 수열 찾기
	int i = n-1;
    while(i > 0 && a[i-1] >= a[i]) i -=1;
    if(i <=0) return false;
    int j = n-1;
    // 뒤집기 시작
    while(a[j] <= a[i-1]) j -= 1;
    // 없는 경우 swap(a[i-1] , a[i-1])
    swap(a[i-1], a[j]);
    j = n-1;
    while(i < j){
    	swap(a[i], a[j]);
        i += 1; j -= 1;
    }
    return true;
}

https://www.acmicpc.net/problem/10972
다음 순열

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool next_permutation(int n, vector<int>& a) {
	int index = n - 1;
	while (index > 0 && a[index - 1] >= a[index]) index -= 1;
	if (index == 0) return false;
	int j = n - 1;
	while (a[j] <= a[index - 1]) j -= 1;
	swap(a[index - 1], a[j]);
	j = n - 1;
	int i = index;
	while (i < j) {
		swap(a[i], a[j]);
		i += 1;
		j -= 1;
	}
	return true;
}
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if (next_permutation(n, a)) {
		for (int i = 0; i < n; i++) {
			cout << a[i] << ' ';
		}
		cout << '\n';
	}
	else
		cout << -1 << '\n';
	return 0;
}

이전 순열

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool prev_permutation(int n, vector<int>& a) {
	int index = n - 1;
	while (index > 0 && a[index - 1] <= a[index]) index -= 1;
	if (index == 0) return false;
	int j = n - 1;
	while (a[j] >= a[index - 1]) j -= 1;
	swap(a[index - 1], a[j]);
	j = n - 1;
	int i = index;
	while (i < j) {
		swap(a[i], a[j]);
		i += 1;
		j -= 1;
	}
	return true;
}
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if (prev_permutation(n, a)) {
		for (int i = 0; i < n; i++) {
			cout << a[i] << ' ';
		}
		cout << '\n';
	}
	else
		cout << -1 << '\n';
	return 0;
}

https://www.acmicpc.net/problem/10974
모든 순열

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 1; i <= n; i++) {
		a[i - 1] = i;
	}
	for (int i = 0; i < n; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';
	while (next_permutation(a.begin(), a.end())) {
		for (int i = 0; i < n; i++) {
			cout << a[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/10819
차이를 최대로

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using  namespace std;
bool next_permutation(int n, vector<int>& a) {
	int index = n - 1;
	while (index > 0 && a[index - 1] >= a[index]) {
		index -= 1;
	}
	if (index == 0) {
		return false;
	}
	int j = n - 1;
	while (a[j] <= a[index - 1]) {
		j -= 1;
	}
	swap(a[index - 1], a[j]);
	j = n - 1;
	int i = index;
	while (i < j) {
		swap(a[i], a[j]);
		i += 1;
		j -= 1;
	}
	return true;
}
int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a.begin(), a.end());
	int ans = 0;
	do {
		int temp = 0;
		for (int i = 0; i < n - 1; i++) {
			temp += abs(a[i] - a[i + 1]);
		}
		if (temp > ans) {
			ans = temp;
		}
	} while (next_permutation(n, a));
	printf("%d\n", ans);
	return 0;
}

https://www.acmicpc.net/problem/10971
외판원 순회 2

시간 복잡도가 N x N!로 나오는데 N의 최대 값이 10이므로 O(3천만)으로 가능하다.

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 20000000
using namespace std;
int d[10][10];
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		a[i] = i;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> d[i][j];
		}
	}
	int ans = MAX;
	do {
		int temp = 0;
		for (int i = 0; i < n - 1; i++) {
			temp += d[a[i]][a[i + 1]];
			if (d[a[i]][a[i + 1]] == 0)
				temp += MAX;
		}
		temp += d[a[n - 1]][a[0]];
		if (d[a[n - 1]][a[0]] == 0) {
			temp += MAX;
		}
		if (ans > temp) {
			ans = temp;
		}
		if (temp < ans) ans = temp;
	} while (next_permutation(a.begin(), a.end()));
	cout << ans << endl;
	return 0;
}

염주 순열, 시작점이 같아도 된다

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[20][20];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }

    vector<int> d(n);
    for (int i=0; i<n; i++) {
        d[i] = i;
    }

    int ans=2147483647;

    do {
        bool ok = true;
        int sum = 0;
        for (int i=0; i<n-1; i++) {
            if (a[d[i]][d[i+1]] == 0) {
                ok = false;
            } else {
                sum += a[d[i]][d[i+1]];
            }
        }
        if (ok && a[d[n-1]][d[0]] != 0) {
            sum += a[d[n-1]][d[0]];
            if (ans > sum) ans = sum;
        }
    } while (next_permutation(d.begin()+1, d.end()));

    printf("%d\n",ans);
    return 0;
}

https://www.acmicpc.net/problem/6603
로또 (컴비네이션의 구현, next_permutation으로 구현 가능)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n;
	while(true) {
		cin >> n;
		if (n == 0) break;
		vector<int> d(n);
		for (int i = 0; i < n; i++) {
			cin >> d[i];
		}
		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			if (i < 6) a[i] = 1;
			else a[i] = 2;
		}
		do {
			for (int i = 0; i < n; i++) {
				if (a[i] == 1)
					cout << d[i] << ' ';
			}
			cout << '\n';
		} while (next_permutation(a.begin(), a.end()));
		cout << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/14888
연산자 끼워넣기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> d(n);
	for (int i = 0; i < n; i++) {
		cin >> d[i];
	}
	vector<int> a;
	for (int i = 1; i <= 4; i++) {
		int t;
		cin >> t;
		for (int j = 0; j < t; j++) {
			a.push_back(i);
		}
	}
	vector<int> ans;
	do {
		int temp = d[0];
		for (int i = 0; i < a.size(); i++) {
			switch (a[i]) {
			case 1: temp += d[i + 1];
				break;
			case 2: temp -= d[i + 1];
				break;
			case 3: temp *= d[i + 1];
				break;
			case 4: temp /= d[i + 1];
				break;
			default:
				break;
			}
		}
		ans.push_back(temp);
	} while (next_permutation(a.begin(), a.end()));
	sort(ans.begin(), ans.end());
	cout << *(ans.end() - 1) << '\n' << *ans.begin() << '\n';
	return 0;
}

벡터 출력시 end() - 1 임에 주의하자

Recursive

다이나믹 프로그래밍에서 다시 다룬다.
재귀 유의할 사항
(1) 종료 조건
(2) 맞출 경우
(3) 그 외 경우(진행)

https://www.acmicpc.net/problem/9095
1, 2, 3 더하기

#include <iostream>
using namespace std;

int go(int sum, int goal);

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		int ans = go(0, n);
		cout << ans << '\n';
	}
	return 0;
}

int go(int sum, int goal) {
	if (sum > goal) return 0;
	if (sum == goal) return 1;
	int now = 0;
	for (int i = 1; i <= 3; i++) {
		now += go(sum + i, goal);
	}
	return now;
}

https://www.acmicpc.net/problem/1759
암호 만들기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int l, c;

bool check(string &word) {
	int ja = 0;
	int mo = 0;
	for (char x : word) {
		if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u')
			mo += 1;
		else
			ja += 1;
	}
	return (mo >= 1 && ja >= 2);
}

void go(int l, vector<char>& a, string word, int index) {
	if (word.length() == l) {
		if (check(word)) {
			cout << word << '\n';
		}
		return;
	}
	if (index >= c)
		return;
	go(l, a, word + a[index], index + 1);
	go(l, a, word, index + 1);
}

int main() {
	cin >> l >> c;
	vector<char> a(c);
	for (int i = 0; i < c; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	go(l, a, "", 0);
	return 0;
}

뽑을까 말까 결정하기

https://www.acmicpc.net/problem/6603
로또(재귀로 풀기) - 이전과 마찬가지로 뽑을까 말까를 결정 길이가 되면 끝

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int k;
vector<int> lotto;

void go(vector<int>& a, int index) {
	if (lotto.size() == 6) {
		for (int num : lotto) {
			cout << num << ' ';
		}
		cout << '\n';
		return;
	}
	if (index >= a.size())
		return;
	lotto.push_back(a[index]);
	go(a, index + 1);
	lotto.pop_back();
	go(a, index + 1);
}

int main() {
	while (true) {
		cin >> k;
		if (k == 0) break;
		vector<int> a(k);
		for (int i = 0; i < k; i++) {
			cin >> a[i];
		}
		go(a, 0);
		cout << '\n';
	}
	return 0;
}

전역으로 선언 = 넣어줬으면 다시 빼줘야함, 리턴될 때 차근차근 하나씩 뺀다.

https://www.acmicpc.net/problem/1182
부분수열의 합
공집합인 경우 주의, 반드시 끝까지 가야 모든 경우 확인 가능

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, s;

int go(vector<int>& a, int sum, int index) {
	if (index == n) { // 어차피 안더하는 경우가 있으므로 끝까지..
		if (sum == s) return 1;
		else return 0;
	}
	int now = 0;
	now += go(a, sum + a[index], index + 1);
	now += go(a, sum, index + 1);
	return now;
}

int main() {
	cin >> n >> s;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int ans = go(a, 0, 0);
	if (s == 0)
		ans -= 1; // 공집합인 경우를 제 해야 해..
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/14501
퇴사

#include <iostream>
using namespace std;
int t[21];
int p[21];
int n;
int ans = 0;
void go(int day, int sum) {
    if (day == n + 1) {
        if (ans < sum) ans = sum;
        return;
    }
    if (day > n) {
        return;
    }
    go(day + 1, sum);
    go(day + t[day], sum + p[day]);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> p[i];
    }
    go(1, 0);
    cout << ans << '\n';
    return 0;
}

https://www.acmicpc.net/problem/14888
연산자 끼워넣기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

pair<int, int> go(vector<int>& a, int index, int current, int plus, int minus,
	int mul, int div) {
	if (index == a.size()) {
		return make_pair(current, current);
	}
	vector<pair<int, int>> result;
	if (plus > 0) {
		result.push_back(go(a, index + 1, current + a[index], plus - 1, minus
			, mul, div));
	}
	if (minus > 0) {
		result.push_back(go(a, index + 1, current - a[index], plus, minus - 1
			, mul, div));
	}
	if (mul > 0) {
		result.push_back(go(a, index + 1, current * a[index], plus, minus
			, mul - 1, div));
	}
	if (div > 0) {
		result.push_back(go(a, index + 1, current / a[index], plus, minus
			, mul, div - 1));
	}
	auto ans = result[0];
	for (auto p : result) {
		if (ans.first < p.first) {
			ans.first = p.first;
		}
		if (ans.second > p.second) {
			ans.second = p.second;
		}
	}
	return ans;
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int p, min, mul, div;
	cin >> p >> min >> mul >> div;
	auto ans = go(a, 1, a[0], p, min, mul, div);
	cout << ans.first << '\n' << ans.second << '\n';
	return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> result;

void go(vector<int>& a, int index, int current, int plus, int minus,
	int mul, int div) {
	if (index == a.size()) {
		result.push_back(make_pair(current, current));
	}
	if (plus > 0) {
		go(a, index + 1, current + a[index], plus - 1, minus
			, mul, div);
	}
	if (minus > 0) {
		go(a, index + 1, current - a[index], plus, minus - 1
			, mul, div);
	}
	if (mul > 0) {
		go(a, index + 1, current * a[index], plus, minus
			, mul - 1, div);
	}
	if (div > 0) {
		go(a, index + 1, current / a[index], plus, minus
			, mul, div - 1);
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int p, min, mul, div;
	cin >> p >> min >> mul >> div;
	go(a, 1, a[0], p, min, mul, div);
	auto ans = result[0];
	for (auto p : result) {
		if (ans.first < p.first) {
			ans.first = p.first;
		}
		if (ans.second > p.second) {
			ans.second = p.second;
		}
	}
	cout << ans.first << '\n' << ans.second << '\n';
	return 0;
}

https://www.acmicpc.net/problem/15658
연산자 끼워넣기 (2)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<long long> box;
void go(int index, int n, long long result,
	vector<int> &a,int add, int min, int mul, int minu) {
	if (index == n) {
		box.push_back(result);
		return;
	}
	if(add > 0)
		go(index + 1, n, result + a[index], a, add - 1, min, mul, minu);
	if(min > 0)
		go(index + 1, n, result - a[index], a, add , min - 1, mul, minu);
	if(mul > 0)
		go(index + 1, n, result * a[index], a, add , min, mul - 1, minu);
	if(minu > 0)
		go(index + 1, n, result / a[index], a, add , min, mul, minu - 1);
}
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<int> op(4);
	for (int i = 0; i < 4; i++) {
		cin >> op[i];
	}
	go(1, n, a[0], a, op[0], op[1], op[2], op[3]);
	auto p = minmax_element(box.begin(), box.end());
	cout << *p.second << endl;
	cout << *p.first << endl;
	return 0;
}

0개의 댓글