백준[14888] 연산자 끼워넣기

삼성 SW역량테스트 문제이다.

링크 : https://www.acmicpc.net/problem/14888

순열을 사용한 모든 경우를 탐색하면 해결할 수 있다. 

자료를 저장해서 어떻게 순열을 해야할지가 중요할 수 있다. 필자는 한배열에 각 연산자를 모두 저장하였으며

0 , 1, 2, 3 을 각각 더하기, 빼기, 곱하기, 나누기로 생각하여 입력에서 받은 모든 갯수를 한 배열에 순서대로 저장하였다.

이 저장값을 기본으로 나올 수 있는 모든 순열에따라 계산을 진행하여 최대값과 최소값을 갱신하여 답을 구하였다.

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
#include<functional>
#include<deque>
 
using namespace std;
 
int n, arr[12], visit[12],k,k2,visit2[12],arr2[12],ans=-1000000010,ans2=1000000010;
 
void dfs(int a) {
    if (a == n - 1) {
        int chk = arr[0];
        for (int i = 0; i < n - 1; i++) {
            //printf("%d ", arr2[i]);
            if (arr2[i] == 0) {
                chk = chk + arr[i + 1];
            }
            else if (arr2[i] == 1) {
                chk = chk - arr[i + 1];
            }
            else if (arr2[i] == 2) {
                chk = chk * arr[i + 1];
            }
            else if (arr2[i] == 3) {
                chk = chk / arr[i + 1];
            }
        }
        ans = max(ans, chk);
        ans2 = min(ans2, chk);
        //printf("\n");
        return;
    }
    for (int i = 0; i < n-1; i++) {
        if (visit2[i] == 0) {
            visit2[i] = 1;
            arr2[a] = visit[i];
            dfs(a + 1);
            visit2[i] = 0;
        }
    }
}
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    for (int i = 0; i < 4; i++) {
        int a;
        scanf("%d", &a);
        for (int j = 0; j < a; j++) {
            visit[k] = k2;
            k++;
        }
        k2++;
    }
 
    //for (int i = 0; i < n - 1; i++) printf("%d ", visit[i]);
    //printf("\n\n");
    dfs(0);
    printf("%d\n%d", ans, ans2);
    return 0;
}