2017년 하반기 채용 문제로 나온 연산자 끼워넣기 문제입니다. 이미 SW 역량 테스트 공부를 해보셨던 분들은 아시겠지만, 삼성전자에서는 채용 문제로 완전 탐색, DFS, BFS 문제를 굉장히 많이 출제하고 있는 것을 알 수 있습니다. 어떻게 보면 이 3가지는 비단 알고리즘 문제 뿐만 아니라, 실무에서도 사용할 수 있는 개념이기 때문에 이런 유형의 시험이 많은 것은 나쁘지 않다고 생각합니다.
연산자의 우선순위를 무시하고, 주어진 수 사이에 연산자를 끼워넣어 계산했을 때 나올 수 있는 최댓값과 최솟값을 구하는 문제입니다. 나올 수 있는 숫자는 총 11개이므로 연산자는 10개이고, 나올 수 있는 가장 큰 경우의 수는 각 부호에 대해 $10! / (A_+)!(A_-)!(A_*)!(A_/)!$ 가 됩니다. 그러므로 완전 탐색을 통해 문제를 해결할 수 있음을 알 수 있습니다.
완전 탐색을 하는 방법에는 dfs로 하는 방법과, STL을 이용할 수 있는 환경에서는 next_permutation 이라는 함수를 통해 모든 경우를 다 테스트해볼 수 있습니다. 하단 소스코드에는 next_permutation 으로 푸는 방법을 올려놓았습니다. 추가글로 dfs로 푼 소스코드도 첨부하겠습니다. (추가된 소스를 보려면 하단의 빨간색 버튼을 누르면 됩니다.)
그렇게 해서 모든 경우를 다 따져 최대, 최소를 구하면 됩니다. 여기서 조심해야 되는 경우가 있는데, -10억 ~ 10억 의 값을 가질 수 있으므로 최댓값을 비교하는 변수는 -10억보다 작은 값을 가진 상태에서 시작, 최솟값은 10억보다 큰 값을 가진 상태에서 시작해야 한다는 점입니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, k, no[11], ari[11], ap = 0, ans1 = -2e9, ans2 = 2e9;
cin >> n;
for (int i = 0; i < n; i++) cin >> no[i];
for (int i = 0; i < 4; i++) {
cin >> k;
for (int j = 0; j < k; j++) ari[ap++] = i;
}
do {
int cmp = no[0];
for (int i = 0; i < ap; i++) {
if (ari[i] == 0) cmp += no[i + 1];
if (ari[i] == 1) cmp -= no[i + 1];
if (ari[i] == 2) cmp *= no[i + 1];
if (ari[i] == 3) cmp /= no[i + 1];
}
ans1 = max(ans1, cmp);
ans2 = min(ans2, cmp);
} while (next_permutation(ari, ari + ap));
cout << ans1 << "\n" << ans2;
}