주어진 수와 연산자로 가능한 모든 경우 실행한 후 최댓값,최솟값 구하는 문제다.
모든 경우 확인해야 하므로 완전탐색+
중간중간에 연산자 바꾸면서 계산하므로 되돌아 와야함
-> 백트래킹 필요
Backtracking
- DFS와 코드가 유사하지만 이전 상태로 돌리는 코드가 추가된다.
- 이 문제에선 연산자를 바꿔가며 계산해야 하므로 이 부분을 되돌려야 한다.
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int n, maxval = -100000001, minval = 1000000001;
int arr[12];
int opers[4];
void bt(int i, int res)
{
if (i == n)
{
maxval = max(res, maxval);
minval = min(res, minval);
return;
}
for (int j = 0; j < 4; j++)
{
if (opers[j] > 0)
{
opers[j]--; //연산자 사용하므로 개수 빼준다
if (j == 0)
{
bt(i + 1, res + arr[i]); //매개변수 전달시 i++ 형태로 전달하면 안된다!!
}
else if (j == 1)
{
bt(i + 1, res - arr[i]);
}
else if (j == 2)
{
bt(i + 1, res * arr[i]);
}
else if (j == 3)
{
bt(i + 1, res / arr[i]);
}
opers[j]++; //이전 상태로 되돌린다.
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
for (int i = 0; i < 4; i++)
{
cin >> opers[i];
}
bt(1, arr[0]); //시작과 동시에 수 사용하므로 1을 매개변수로 넘겨준다.
cout << maxval << '\n'
<< minval << '\n';
return 0;
}