4008. [모의 SW 역량테스트] 숫자 만들기

백준 14888 연산자 끼워넣기와 똑같은 문제.

+ - * / 개수에 맞게 순열을 구한 후, 차례대로 계산하면 되는 문제.

#include <stdio.h>
#include <string.h>
 
int num[5];
int arr[12];
int visit[12];
int N, MIN, MAX;
 
 
void DFS(int a, int b, int c, int d, int n)
{
    if (num[1] < a || num[2] < b || num[3] < c || num[4] < d)
        return;
 
    if (num[1] == a && num[2] == b && num[3] == c && num[4] == d)
    {
        int NUM = arr[0];
 
        for (int i = 0; i < n; i++)
        {
            switch (visit[i])
            {
            case 1:
                NUM = NUM + arr[i + 1];
                break;
            case 2:
                NUM = NUM - arr[i + 1];
                break;
            case 3:
                NUM = NUM * arr[i + 1];
                break;
            case 4:    
                NUM = NUM / arr[i + 1];
                break;
            }
        }
 
        if (NUM < MIN)
            MIN = NUM;
        if (NUM > MAX)
            MAX = NUM;
 
        return;
    }
    visit[n] = 1;
    DFS(a + 1, b, c, d, n + 1);
    visit[n] = 2;
    DFS(a, b + 1, c, d, n + 1);
    visit[n] = 3;
    DFS(a, b, c + 1, d, n + 1);
    visit[n] = 4;
    DFS(a, b, c, d + 1, n + 1);
 
    return;
}
 
int main()
{
    int Test_Case;
    scanf("%d", &Test_Case);
 
    for (int T = 1; T <= Test_Case; T++)
    {
        MIN = 987654321;
        MAX = -987654321;
        memset(arr, 0, sizeof(arr));
        memset(visit, 0, sizeof(visit));
        scanf("%d", &N);
 
        for (int i = 1; i <= 4; i++)
            scanf("%d", &num[i]);
 
        for (int i = 0; i < N; i++)
            scanf("%d", &arr[i]);
 
 
        DFS(0,0,0,0,0);
 
        printf("#%d %d\n",T, MAX-MIN);
    }
 
    return 0;
}